There are three major music publishers (UMG, Sony, Warner). As long as you have contracts with them, you'll have nearly everything.

Spotify's not the only competing service that has almost everything. Tidal, Google Play Music, Apple Music, they've all managed to get a deal with those publishers. Smaller players like Deezer even manage to offer the same service to 180+ countries (compared to Spotify's 20).

Netflix and others would also have nearly everything if the majority of the movies was produced by three publishers.