The reason you get this error is that the signing key for Spotify's debian repository changed between "several weeks ago" and now. We distributed a new key with version 1.0.59 I think, but since you have a version older than that, you never got the new key and now your OS _correctly_ warns you that it can't verify that package is authentic.
Yesterday, Spotify was released as a snap package, which is supported on Mint as well. Follow the instructions on https://docs.snapcraft.io/core/install-linux-mint to install snapd on Mint. Then use snap to install spotify. To not confuse spotify from the debian package with the snap package, remove the old spotify debian package as well. In short: