I drove across the Andes in Argentina and Chile twice. Highest I got was 4,600m above sea level. At 2,500m the engine in the Fiat Sienna (1st year) and Ford Escape (2nd year) were both not breathing in enough oxygen. I was flat-out in third just to keep it going at 60 km/h.
Fuel consumption goes through the roof because you have to use way, way more fuel. I think we went from about 400 km of range to about 300 km of range in the little Fiat.
Altitude is bad news for engines.
You sure the lousy fuel economy wasn't just because of the mountains you were climbing? Going uphill is always going to get you worse mileage than cruising on the flats.
A fuel injected engine is only going to inject as much fuel as there is oxygen available to burn it. Less dense air at altitude means less oxygen available means less fuel injected, not more.
And engines are actually more efficient at wide open throttle than at partial throttle, so having to floor it just to produce the same amount of power as at lower elevations should help fuel economy, not hinder it.
HeliDriver is right; the lower air density results in lower power output. With a reduced air intake volume, the engine can't inject as much fuel. In turn, the reduced power output necessitates larger throttle openings to climb the grade, harming fuel consumption.
Well, that's not quite what I was saying. Larger throttle openings should be
good for fuel economy, not bad. That's why BMW got rid of the throttle plate completely and went with their Valvetronic instead. The engine is running at WOT all the time (well, actually there is no throttle, but it's kind of the same thing) and they realized something like a 10% improvement in fuel economy, IIRC.
I think there are two separate discussions to be had here: power loss at altitude is the easy one, but fuel economy at altitude is the more interesting one.
Maybe if the car is so underpowered to start with that you wind up using both a larger throttle opening
and a lower gear, then you'd see a decrease in fuel economy. But if it's a question of being at the same speed, same gear, same rpm in a constant cruise, then the engine is making the same horsepower (oops, actually less horsepower because of the reduced wind resistance), just at a larger throttle opening, which is not a bad thing.
People usually think in terms of the "gas" pedal, which it really isn't: it's more of an "air" pedal. Just because your foot is to the floor (at altitude) doesn't mean the engine is getting more gas (than it would at sea level.)