I just installed (06/19/2017) Spotify so should have newest version.
click on down arrow its to the right of profile button in upper right of page.
click on settings. Scroll down to end of settings then click on "advanced settings"
Scroll down to "Startup and Window Behaviour" Subhead says "Open Spotify automatically.
Down arrow gives three choices. Choose "NO". Restart.. Spotify should not start.
And shortcut on desktop put there on installation should now work
I had this problem and changing the settings and restarting didn't work. Go to task manager<startup<spotify and select disable then restart. That worked for me.