I did some measurements on shazam and it seems to send about 7kb/minute, which corresponds to 300MB/month, i.e. no big deal. I suppose it helps that shazam was designed in the age of expensive bandwidth.