The non-linear relationship can be obtained from the conservation of momentum as,
$$\rho v\,\mathrm{d}v=-\mathrm{d}p\tag{1}$$
with $\rho$ the density, $v$ the velocity and $p$ the pressure. It also turns out that the pressure can be related to the density (assuming an isentropic flow, which describes a slowly changing flow rather than a very rapid change):
$$\frac{\mathrm{d}p}{p}=\gamma\frac{\mathrm{d}\rho}{\rho}\to\,\mathrm{d}p=\gamma RT\,\mathrm{d}\rho=a^2\,\mathrm{d}\rho\tag{2}$$
where we used the ideal gas law to eliminate $p/\rho$ and $a$ is the speed of sound.
Combining these two equations yields,
$$-M^2\frac{\mathrm{d}v}{v}=\frac{\mathrm{d}\rho}{\rho}\tag{3}$$
where $M=v/a$ is the Mach number.
When $M$ is very small (e.g., much less than 1), the density is roughly constant as the left side of Eq 3 is approximately 0 due to the squared mach number. When $M\simeq1$, then the density increases at the same rate as the velocity and when $M\gg1$, then the density changes much faster than velocity.
On the intuitive side, what is happening is that some of the energy of the aircraft is being used to compress the air molecules in front/around it, which is then locally increasing the density. So this is really more of a "push" (by the airplane) than air molecules "bouncing" off each other as you describe in the linked question.
