Yup, good link Rev. Cover tunes require the payment of the mechanical royalty to be legal.

In practice, this is rarely enforced. But I've heard of horror stories of ASCAP reps going by the name of "Guido" showing up at nightclubs and making the club owner pay under threat of concrete overshoes.

And as a friend of mine recently found out, the details of actually getting the mechanical royalties licensed and paid for is rather tricky. There are some clearing houses for this which will cover several labels, but not everyone is covered by the clearing houses. For instance, it takes some working finding the right people to pay to cover an Eagles tune because each member retains their own rights.

Edit: Rev's link didn't seem to work the second time I tried it...