Sound waves can propgate through solids, liquids and gases. I think one should say that sound waves are mechanical waves and not vice versa because mechanical waves are general and sound waves are specific.
I believe the short answer to the OP question is: Hooke's Law.
No matter what the medium is, if you have a situation where distention increases the counter-force in a linear fashion, you will have a medium that allows wave propagation.
Mechanical waves are energy propagations across a structure through compression and stretching of the connected molecules making up the structure. The actual wave traveling is just the part of the structure that's currently reacting to the forces in order of next touching molecule and not the structure itself being moved