I was wondering what the restrictions on the songs by Elvis Presley are. I want to have a power up in my game that I call "Elvis Parsley" and he attacks by singing and dancing, but when he comes on, I want to have Elvis music playing in the background. It's going to be either shareware, or commercial if I can find a publisher.

Above and beyond the copyright issues involved with using the music, 'Elvis Presley' is a registered trademark (see here), which pretty much rules out using the name (or even a variation thereof).

Also note that Presley Enterprises does actively defend their IP.

(As always, IANAL)

For music, you will need licenses to use both the master (the sound recording) and the musical composition. For the specifics on these licenses, go here.

Bear in mind that the Elvis estate is pretty uptight about use of his name and likeness. The right of publicity right of celebrities is a quasi-intellectual property right, and while there are some first amendment protections with regard to parody you may still have to fight it in court. They've sued over stupider things.

Contact a lawyer if you plan on doing it. Short answer is "not without permission".

The restrictions are that you will have to negotiate a license fee or royalty for the use of the music from the current the copyright holder. A quick Google bought up this site http://www.elvis.com/licensing/. It appears that they own (or did own) the rights to the music, but not the actual recordings of Elvis, which seem to be owned by Sony BMG (who bought RCA the original owners). I have not done a thorough search so this info could be out of date. You will need to find the correct companies in order to negotiate with them.

If you want to have a composer produce a version of an Elvis hit for use in your game you will need a license from the owners of the music. If you need to use a specific recording you will need a license from the company that owns that recording AND may also need a separate agreement with the owners of the music - again, I am not a music industry lawyer so I don't know exactly who you need a license from. Unless you know you will likely need to hire a lawyer with experience in music licensing to help you.