Descargar paquete de spotify de su repositorio oficial, o del directorio de descargas
Una vez descargado instalarlo con dpkg
dpkg -i Descargas/spotify-client-0.9.17_0.9.17.8.gd06432d.31-1_amd64.deb
***Precaución***
No hacerlo de modo gráfico ya que se queda colgado a mitad de la instalación, instalar con dpkg
En kali me da este error
spotify: error while loading shared libraries: libgcrypt.so.11: cannot open shared object file: No such file or directory
Se soluciona instalando la librería libgcrypt11, puedes descargarla desde su repositorio oficial o del directorio de descargas
Una vez descargado ejecutar:
dpkg -i libgcrypt11_1.5.0-5+deb7u1_amd64.deb