Oxygen density is also proportional to the density of the fluid, so this should be a wash.

Yeah I suspect this is it. The density is inversely proportional to temperature and drag is proportional to to density. Even if the engine is more efficient (in a steady state) with denser air, the relationship is probably sub-linear.

Colder weather reduces fuel efficiency because during warmup, extra fuel is injected into the cylinders to maintain performance, since it's harder to get ignition when the air is colder. In other words, better to waste some fuel than to hit the gas and have a lot less acceleration than usual.

My car is markedly less efficient in winter on short trips, even though England doesn't moves vertically with the seasons. Over longer journeys this phenomenon is much less of a problem.

The engine's preferred operating temperature is much higher than any reasonable air temperature, and until that point is reached the engine oil will be less lubricative and the fuel (particularly in the case of diesel) less inclined to combust. It will naturally take longer to reach that preferred temperature when it is cold outside, because not only is the air cold but the engine is also this big lump of cold metal, absorbing the heat of combustion and pulling it away from the cylinder where it is needed.

In a modern car, the ECU controls the air intake pressure, so all higher altitude would mean is that the turbo system would spin a bit faster.

The sparse atmosphere robs the engine of power, but that doesn't mean that it is less efficient, I think that matters on the car/driver.

Personally, high altitude driving helps my fuel economy -- I would speculate that it's due to decreased air resistance and the lack of power forcing me to drive a little more conservatively.