John Rennie has provided an exact mathematical treatment of the equations behind the calculation of the speed of sound. I don't want to detract from that treatment, and of course the Wikipedia articles we both draw from provide a broader treatment; but an intuitive understanding of the 'why' has been equally helpful for me, in the past. The following is my attempt to comprehend and explain the 'why' to the question.
There are more factors affecting the speed of sound in a substance other than the density of the medium. This is reflected in the equations for determining the speed of sound, most notably the presence of the bulk modulus and shear modulus in different places in the equations for sound in a solid and a liquid.
The bulk modulus is a measure of a substance's resistance to uniform compression. It is measured in pascals, which is the same unit for pressure. Uniform compression means the substance is experiencing equal pressure in all directions (as in atmospheric or underwater pressure). Thus, the bulk modulus tells you how much the substance will shrink — that is, decrease in volume and increase in density — when subject to a given pressure.
Now the shear modulus is a measure of stiffness. Specifically, it measures how a material responds to forces acting in opposite directions, as in friction holding a block in place or moving your hands away from each other to tear a piece of paper in half. Imagine trying to subject a liquid or a gas to a shearing force and it becomes clear that the shear modulus is meaningless for forms of matter other than solids. Simply put, gasses and liquids don't resist shearing forces.
For that reason, the shear modulus factors into the speed of sound in a solid, but not into the speed of sound in a liquid. Wikipedia summarizes this on the speed of sound section linked to above as:
In a fluid the only non-zero stiffness is to volumetric deformation (a fluid does not sustain shear forces).
In a more general sense, different mediums have different responses to different forces. Wave propagation is essentially a transfer of energy through a medium — that energy transfer is accomplished by a compression force at the molecular level.
For a macroscopic metaphor, imagine propagating a wave through a slinky. That slinky looks to be made of steel, but it is still very flexible, which is to say it is not stiff. Imagine repeating the experiment in that video with a solid steel bar of the same width and length. Assuming the students could still move the mass with the same vigor, you would not be able to observe either a transverse or a longitudinal wave motion. The solid steel, despite being the same material with the same density as the slinky, is much stiffer, and therefore propagates waves very differently.
Similarly, the difference in the stiffness between liquid mercury and solid iron are enough to overcome the greater density of the mercury to make sound propagate faster in the iron.