I have a playlist I maintain that has nearly 3,000 tracks. When I shuffle this playlist, rather that shuffling the whole thing, Spotify only shuffles within a range of ~150 tracks (based off of the playlist order).
Example: the playlist is sorted alphabetically by artist. If I pick a song by an artist that starts with the letter 'B', then when on Shuffle mode, it WILL shuffle, but it will only play random songs by more 'B' artists (and perhaps some 'A' and 'C' artists). It will NOT shuffle the whole set of tracks.
It's a niche case, but it makes maintaining a playlist for every song I've ever loved a little useless. Size seems like it's throwing off your shuffle algorithm.
Error occurs on mobile (LG G5, up to date Spotify app) as well as on the desktop app.