I'm open to correction on this but I think I'm right:

To my knowledge, U.S. copyrights only apply to the actual song melody and lyrics. In fact, I've seen books and websites which make the chords, even with the full song title, freely available. I believe that you can use a song's chords and title without paying any royalties.

There are many examples where arrangers have danced around this - my Yamaha 9000 Pro's music database includes setups for famous songs where the title is slightly altered as a legal precaution, like "Proud of Mary" for the song "Proud Mary", etc.

I saw that the Yamaha PSR-K1's song bank includes the song "Englishman in New York" by Sting complete, and I'm sure that fees were paid for that.