If you make all of the idealizing assumptions, the power output of an internal combustion (otto cycle) engine is: Cp*(T3-T4)*mdot (per cylinder) where Cp is the specific heat of air at const pressure, mdot is the mass flow rate of air through the device, T3 is the air temp as the piston begins down-stroke, and T4 is the air temp at the end of the down-stroke.
Density goes down exponentially with altitude, so if T3 and T4 were constant, the power would indeed scale with density. But T3 and T4 won't be the same at all altitudes. First, for ideal gas & isentropic process (so everything is ideal and happy), T4 and T3 are related--if I know one I can find the other. So T3 is reached by burning fuel. The relation for this is qdot = Cv*(T3-T2)*mdot, where Cv is the specific heat of air at const volume, T2 is the air temp as the piston reaches the top of its stroke (like right before the spark fires), and qdot is the heat/time generated by burning fuel. To raise qdot, you'd want more airflow and more fuel. So as the amount of airflow drops b/c density is falling, you will also get less energy from each 4stroke cycle.
So basically I think the underlying reason for what you're observing is that at altitude, you also generate less energy per cycle in addition to simply having less mass flow.
But horsepower isn't it. Owing to the reduced density, prop performance and lift will similarly be reduced meaning the plane's performance will be worse across the board.