Yes, songs can be in more than one playlists - playlists can even be in more than one playlist (it works hierarchically).

When you remove a song from a playlist, it decrements the "reference count" (ie, the number of times that song is referred to in the various playlists on the empeg) - when this gets to zero, the song is removed from the empeg at the next synchronise.

Hugo