Only the first approximately 100-200 of the songs actually delete. The remainder of them are still there, but no longer selected.
I am not sure of the exact numbers, but this is reproduceable. (My first thought was it must be exactly 100, because of paged API requests, but apparently not.)
This only applies to desktop, as there does not seem to be a way to select multiple songs on web (It would be great if that could be fixed, but one issue at a time).
Use case: on Fridays I drag a whole bunch of new releases and playlists into a temp playlist and then weed it out later. (Operating on playlists this large is painfully laggy now, but I don't have a specific bug to point to there.)