I hadn't realised that the wifi->address mapping was so publicly available. That means a list of wifi addresses that you've connected your phone to is also a location history. :(
Which is why Android restricts getting the current wifi SSID (WifiManager.getConnectionInfo()) or the nearby wifi SSIDs (WifiManager.getScanResults()) to apps with the ACCESS_COARSE_LOCATION or ACCESS_FINE_LOCATION permissions. If an application doesn't have permission to know your location, it's also not allowed to know your wifi network's name.
I guess good time to point out XPrivacyLua[0], a privacy/permissions manager which should be default in Android imo (without having to root/install Xposed etc). But for the power users out there, worth it.