Density is indeed proportional to pressure in an ideal gas at a fixed temperature. So, when Bernoulli's principle states that pressure varies with the square of velocity assuming a fixed density, the conclusion seems to contradict the premise. However, even very small changes in pressure can have significant effects.
Consider the pressure difference required to lift a large airplane weighing 2 meganewtons: With a wing area of 430 $m^2$ (source), a pressure differential of ~4600 $N/m^2$ would be needed. While that may seem like a large pressure differential, keep in mind that atmospheric pressure is 101325 $N/m^2$, so the pressure differential needed to lift the airplane is relatively small: only ~4% of atmospheric pressure. A density variance of 4% in a gas flow can be considered insignificant.
Furthermore, in order for a gas flow to have a significant density change, the velocity change of the flow would have to be very large, at which point the "low Mach number" premise of Bernoulli's equation would no longer hold.
By Bernoulli's equation, that lift pressure calculated above, 4600 $N/m^2$, corresponds to a velocity difference of ~87 m/s, which is getting close to Mach 0.3. Above Mach 0.3 is not considered a low Mach number, so Bernoulli's equation would not apply.
There are variations on Bernoulli's equation that are applicable to compressible flows and take into account density varying within the flow.