I just did a clean re-install and changed my password. Still having the same issue - Spotify is automatically playing songs by KikkiTai and Cholosus (and others from the same playlist). App version 8.5.94 on iPhone.
After the clean re-install and changing password (which did not work), I tried "sign out of all devices" and that seemed to do the trick. For reference, here are the playlists/albums that kept automatically playing: