Song titles are not protected under copyright law. For more on this, see the United States Copyright Office FAQ page. (It’ll also tell you about copyrighting your Elvis sighting, which tickles me to no end!) While your use doesn’t sound problematic, it is possible you could run into trademark issues. That is, some song titles are synonymous with the bands that made them famous and may be protected under trademark law. Remember the “Californication” legal fight between the Red Hot Chili Peppers and Showtime a few years ago? If you intend to publish your project through a traditional publishing house, in-house legal staff can verify your use of the song titles, so go ahead and use the titles in your manuscript without worry. If you’re going to self-publish, you can settle your mind (and CYOB) by verifying your use of the titles with an intellectual property law attorney. I’m just an editor; they’re the ones who can give you the official legal thumbs-up.
Oh, by the way, the publisher won’t think “it’s too much work” at all . . . because most publishing contracts require the author to secure the permissions.