Bicycles, like many machines, are efficient, but a large amount of energy converted by them is not in fact used for their "intended" purpose: The largest energy sink is air/wind resistance, which you can only very marginally improve on a "normal" bike†. However, wind resistance squares in relation to your speed, so maintaining a more leisurely pace would improve your efficiency. For example, people riding on cross-continental tours actually ride pretty slowly compared to e.g. people riding a road bike for training: They do this so that they can put in longer distances over the whole day rather than pushing themselves as hard as possible for e.g. 5 hours and then being destroyed for at least a day.
The second biggest contributor to the bicycle's lost efficiency is rolling resistance, as you seem to already realize; Therefore, getting a bicycle with proper road tires will drastically improve your riding speed and efficiency over riding a bike with heavy-tread mountain bike tires. As a real-life example, I can easily handle 50+ km in a few hours on a 40-year-old ten-speed without really "pushing" myself past my limit but on a mountain bike this would probably kill me.
Lastly, weight is very important when riding over hilly terrain but less important on the flats. However, you stated that you are riding over hilly terrain, so reducing overall bicycle weight might actually make a big difference for you even if it doesn't improve actual mechanical efficiency much: Humans are extremely complicated machines and we only have a very narrow power band, quickly becoming exhausted once we leave this particular "sweet spot" of cadence and load: If your cadence is too high you run out of breath but if your load is too high your body starts using anaerobic power and builds up lactic acid in your muscles, which wears them out.
TL; DR
If you have the money, go look for a decent used road bike (even if it's old, it's likely going to be more efficient than a fancy new mountain bike)-- if not, go look for decent road tires for your current bike. However, no matter what you do, ride your bike at a casual pace because you'll go further without getting worn out.
† You can significantly reduce wind resistance by riding a bike with full fairings but, for your stated purposes, this would be a bit ridiculous.