This kind of memory is certainly possible. And from what I've seen of McCartney - he has a vast repertoire of songs he knows (not just his own) - it seems almost certain that he has this talent. I suspect it's actually a relatively common ability though. I have family members who can remember both the tune and the lyrics of songs after 1 or 2 listens through. This just isn't so noticeable because they're not musicians.
In general, I find what people find easy to remember a fascinating topic. my personal ability to remember song lyrics (and in general auditory information) is awful - I actually can't remember the entire lyrics to single song. I'm sure I could memorise some if I really tried, but it would take me hours of conscious. effort. On the other hand I often recall visual or written information from a single glance, and am very good at book learning and retaining an understanding of system and concepts.