Why does sound travel faster in iron than mercury even though mercury has a higher density?
The speed of sound in a liquid is given by:
$$ v = \sqrt{\frac{K}{\rho}} $$
where $K$ is the bulk modulus and $\rho$ is the density. The bulk modulus of mercury is $2.85 \times 10^{10}\ \mathrm{Pa}$ and the density is $13534\ \mathrm{kg/m^3}$, so the equation gives $v = 1451\ \mathrm{m/s}$.
The speed of sound in solids is given by:
$$ v = \sqrt{\frac{K + \tfrac{4}{3}G}{\rho}} $$
where $K$ and $G$ are the bulk modulus and shear modulus respectively. The bulk modulus of iron is $1.7 \times 10^{11}\ \mathrm{Pa}$, the shear modulus is $8.2 \times 10^{10}\ \mathrm{Pa}$ and the density is $7874\ \mathrm{kg/m^3}$, so the equation gives $v = 5956\ \mathrm{m/s}$.
You give a slightly different figure for the speed of sound in iron, but the speed does depend on the shape and the figure you give, $5130\ \mathrm{m/s}$, is the speed in a long thin rod. There are more details in the Wikipedia article I've linked.
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.
"The speed of sound is variable and depends on the properties of the substance through which the wave is traveling. In solids, the speed of transverse (or shear) waves depend on the shear deformation under shear stress (called the shear modulus), and the density of the medium. Longitudinal (or compression) waves in solids depend on the same two factors with the addition of a dependence on compressibility."
Speed of sound is function of more than just density. Shear modulus for iron is 82 GPa, I haven't found any data on the modulus of Mercury, but certainly it differs and that's the most probable reason.