So I've been having this problem since I downloaded the 6.0.1 android update.
And before even starting, I never saw another app that does this **bleep** on my cellphone storage.
So, sometimes Spotify just "delete" every music that I've saved on the storage, but the musics doesn't just vanish from the playlists and thing, the app just say that I dont have they downloaded, even though I didn't pressed anything to delete them or anything even close to that. After this thing, I just see if they really vanished from the storage, because I didn't really pressed any buttons at all to "delete" them. But then, when I see my cellphone storage, the size that the musics had, still in my cellphone, even though I cannot play them when I have no Internet connection.
I've alredy re-installed spotify and did the same thing with my cellphone. But today it happened AGAIN.
I really can't download any musics anymore because of that, it says that I don't have any space left on my storage.
I also tryed to find spotify folders and I didn't found anything at all.
This might sound that it's a problem with my smarthphone, and I really would understand that if this EVER happened with others applications.