Does Play Music download songs more than once if they are in different playlists?
No.

I went ahead and downloaded my master playlist that contains all my songs, then the other playlists. The latter all took zero time, indicating the songs were not downloaded twice