Is the battery cycle count stored on the battery or the device? I downloaded an app Phone INFO which shows a number of stats, particularly "Battery Discharge Cycles". I want to know if this number is being retrieved from the battery (i.e. it's just the number of cycles for the current battery) or the phone (i.e. it's the sum of the cycles across all batteries the phone has contained). In other words, if I insert a brand new battery, should I expect the count to drop to zero?

Context: I have a Samsung S6, which doesn't allow easily changing the battery. I went to a phone repair shop to have the battery replaced. I left it there for the day and did not observe the process of replacement. Now I suspect that I was scammed and the battery has not been changed. I want to confront the shop and use the cycle count (which is still very high) as evidence, so I'm checking my understanding first.
It seems the issue is that when the battery is replaced, most mom and pop places don’t have the skill or equipment to go in the “root” to reset the counter. It’s akin to not resetting the change oil light on your car. The issue is that some cars use oil life to make other decisions on engine operation, so without resetting the light, performance isn’t fully restored because the computer thinks it’s still old oil and making its decisions based on that. Your battery life, auto shutdown, and battery life remaining display are kind of the same. I bet your phone goes to zero faster than you expect and shuts off, but after leaving it off for a while, you can cut it back on and it’ll show 20-30% or more battery. If so, the thing to do is to keep draining the battery without plugging it in, until after sitting the phone doesn’t even have the juice to try to start, then charge it up to 100, preferably on regular vs fast charge. The life monitor will adjust to the new high and low, and you should have better battery life performance. What’s happened is your phone is basing the full charge and dead capacity off your old battery still, and this process should force it to adapt to your new one.