They know which song is played and how many seconds you are into the song at what time. The only info they need is the playlist of the store to find out your location.

In the UK a lot of chain stores have a "radio" station meaning that they all play the same song at the same time.

My Shazam app (iPhone) has access to location while in use. I assume most people just click “yes” when asked about this.

Mine is on never and the other option is “while using the app”. I have no recollection of choosing the setting either.

Or they can install ultrasound beacons in the stores. They already have access to the microphone for obvious reasons.

Not even ultrasound, just correlate what everybody hears at the same time?

They might just need one data point, if the playlist curator tells them the exact moment at which the song started.