Your parameter $E$ is the bulk modulus, and this is a measure of how compressible the medium is. Easily compressible media like gases have a low value of $E$ while almost incompressible fluids like water have a very high value for $E$.
And there is the answer to your question. Water does indeed have a higher density than air (by a factor of about 800) but it is much, much less compressible than air so the value of $E$ is much, much higher. The end result is that the value of $E/\rho$ is higher in water than air so the speed of sound is greater.
Strictly speaking your equation applies only to gases and liquids. In solids you also need to take account of the shear modulus, and the expression becomes:
$$ v = \sqrt{\frac{E + \tfrac{4}{3}G}{\rho}} $$
where K and G are the bulk modulus and shear modulus respectively. See Why does sound travel faster in iron than mercury even though mercury has a higher density? for more details.