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