Probably the best way would be to split the players into groups and then they each play each other once and gains either a point for a win and nothing for a loss. After everyone has played each other, the two (or three if it's a small group) with the most points go through to the knock out stages. At this point, players are randomly paired up with each other, and the loser is knocked out. The knock outs can be played all the way through to the end, declaring an overall winner.
To decide who gets to pick a song, it could be put down to the flip of a coin. Another way would be to have the best of 3 (with the third song being chosen by the flip of a coin also - if needed).