I guess it's legal because Spotify is a private subscription service and does not use public airwaves like radio so Payola rules do not apply.