Labels deal in sound recordings, which have historically been licensed independently of the underlying music compositions. Most distributors like Spotify will obtain separate licensing for compositions, whether from collecting societies like ASCAP, BMI, or SESAC, and/or through direct deals with artist / publishers themselves.

This setup may seem odd, but but it has historically been used to provide some protection against labels "screwing" artists - b/c although a label takes the sound recording rights and therefore controls royalty payments back to artists for the recording [if any -- after recoupment, etc], the artist typically retains their own publishing rights and can license those separately for $$ not subject to their label deal (though subject to cuts from societies, and their individual deals with publishers etc). This opens up new revenue streams for artists to get paid outside the control of their label: by radio stations/bars/restaurants via PROs, or in sync-right deals for placement in movies or on TV.