Google Music и русские теги?

Тоже искал, но похоже выход — только перезалить.

Да. Всё стирать и заново заливать. Функциональность мюзик менеджера очень ограничена, например, чтобы заново залить удаленную мелодию, надо её перенести в другую папку. При чем это решение написано в оф.справке.

Все теги должны быть в юникоде. Я настроил себе mp3tag, чтобы он при сохранении сам конвертировал все в юникод. Перед заливкой прогоняю все файлы через него. Работает.

«Тихо сам с собою»
Итак, найдено решение. Немного криво, но по другому не получилось.
Делаем из крокозябровых файлов плейлист (клик на первом треке и шифт-клик на последнем, они как раз по имени отсортированы подряд). На андроид-телефоне (наверное, можно и в эмуляторе?) ставим гугль мьюзик апп, помечаем плейлист как доступный в оффлайне.
Через час-полтора, когда все выкачается, идем в /Android/data/com.google.android.music/cache/music, запускаем пакетную переименовывалку тегов и копирование результата на локальный диск, удаляем в гугльмьюзике крокозябровые файлы и заливаем исправленные.
Вот как-то так.

А как вы им пользуетесь, если он из России недоступен?

Вот решение в 2 клика