Does Google tracking go to the device level?
I recently was living in another city, whose local language differs from my own. Due to spotty network coverage, I ended up having to share my phone's hotspot. When I did ads on YouTube all played in my home's language. This all from an ungoogled phone where I haven't really logged in to Google through any apps except the browser.
If such tracking occurs at the device level, how would you even know what to do to prevent it? Pretty much. They try to link devices to a user so they can track you as your browsing swaps from one device to another, its looking at you at a user level. Google have discussed stopping this but I am not aware of them doing it. They do this for both logged in and not users. If interested read about 'Google Signals' as this is the way they are increasingly look to track in the post-cookie future. to stop it... not sure. Avoid Android and use anti-tracking blockers like Ghostery? Not sure how well this latter stuff works or if you just become another persons customer. How "unGoogled" is your phone OS? Do you have GAPPS installed? Nope.
Running microG on CalyxOS You did say you were using your phone as a "hotspot" so identity info may not necessarily be leaking from the phone itself.