"The speed of sound is variable and depends on the properties of the substancedepends on the properties of the substance through which the wave is travellingtraveling. 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.