Not only were there Shazam apps on phones pre the first iPhone, but in the first place Shazam was a service you didn't even need a smartphone for! When I first started using it, they had a telephone number (in the UK, I'm not sure which other countries) to call up while music is playing, and 30 seconds or so later it would text you the song that it detected during the call.

I agree that "combining phone with one of the most popular / best in some ways mp3 player on the market" was a big part of it (with web browsing and video playing equally important), but Shazam wasn't a new thing that iPhones brought us.

(I also agree with danieldk that Shazam just wasn't a significant factor for most people on any devices, before or after iPhones.)