Você deve pular a primeira linha:
awk 'BEGIN { FS=":"
printf "%-10s %-35s %-55s\n", "RANK", "PERFORMER","SONG"
print "=====================================================================\n"}
FNR==1{next}{printf "%-10s %-35s %-55s\n", $1, $3, $2}' songs
Se você não se importar com a ordem de saída, tente:
$ awk -F':' 'FNR==1{next}{a[$5]+=1} END{for(i in a){print i,a[i]}}' songs
Soul 1
Classic 6
Pop 1