Houve algumas boas respostas até agora, mas eu adotaria um método um pouco diferente, bastante semelhante ao que você descreveu originalmente
SELECT
songsWithTags.*,
COALESCE(SUM(v.vote),0) AS votesUp,
COALESCE(SUM(1-v.vote),0) AS votesDown
FROM (
SELECT
s.*,
COLLATE(GROUP_CONCAT(st.id_tag),'') AS tags_ids
FROM Songs s
LEFT JOIN Songs_Tags st
ON st.id_song = s.id
GROUP BY s.id
) AS songsWithTags
LEFT JOIN Votes v
ON songsWithTags.id = v.id_song
GROUP BY songsWithTags.id DESC
Nesta, a subconsulta é responsável por agrupar músicas com tags em 1 linha por música. Isso é então unido a Votos depois. Eu também optei por simplesmente somar a coluna v.votes como você indicou que é 1 ou 0 e, portanto, uma SOMA(v.votes) somará 1+1+1+0+0 =3 de 5 são votos positivos, enquanto SUM(1-v.vote) somará 0+0+0+1+1 =2 de 5 são votos negativos.
Se você tivesse um índice de votos com as colunas (id_song,vote), esse índice seria usado para isso, então nem chegaria à mesa. Da mesma forma, se você tivesse um índice em Songs_Tags com (id_song,id_tag), essa tabela não seria atingida pela consulta.
editar solução adicionada usando contagem
SELECT
songsWithTags.*,
COUNT(CASE WHEN v.vote=1 THEN 1 END) as votesUp,
COUNT(CASE WHEN v.vote=0 THEN 1 END) as votesDown
FROM (
SELECT
s.*,
COLLATE(GROUP_CONCAT(st.id_tag),'') AS tags_ids
FROM Songs s
LEFT JOIN Songs_Tags st
ON st.id_song = s.id
GROUP BY s.id
) AS songsWithTags
LEFT JOIN Votes v
ON songsWithTags.id = v.id_song
GROUP BY songsWithTags.id DESC
