[ugh]

It is impossible to move songs in a playlist to the trash. That can’t be what happened. (“Deleting” songs in a playlist always merely removes them from the playlist.)

The only place where you can directly move songs to the trash is the music library. You must have been browsing the music library and confused it with a playlist.

[blasdel]

Holding down option while pressing delete in a playlist prompts you with the "Move to Trash" / "Keep in Library" deletion dialog.