Does Play Music download songs more than once if they are in different playlists? I have several playlists which overlap in terms of the songs they contain. I have these downloaded on my phone. If a song is in two playlists, will it be stored twice on my phone?
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