I used to work in music and you really do have to clear the lyrics. If you have them on cd you should have the publishing information there - it will be the one with the songwriter information as you need the publisher not the record label. You shouldn't have any problem at all in clearing the lyrics as long as they are not used in a derogatory way. If you go ahead without clearing them, you could end in trouble. Once something has been published, the copyright owners are in a strong position to sue if they fancy it or at least to get royalties.
Anyway, congratulations on being published and lots and lots of luck!
Sue