Ответы справочной службы
Это название склоняется. Верно: Приехал в Кызыл-Кию.
Справочники
§ 67. В соответствии с общим правилом (см. § 33), написание букв на месте безударных гласных в окончаниях устанавливается путем проверки формами слов с тем же окончанием (того же типа склонения), в которых проверяемый гласный находится под ударением, напр.: о´зеро, колен´о, по´ле, полоте´нце (окно´, долото´, лицо´, ружьё); ча´ши, ко´ни (столы´, пни); кни´ге, о кни´ге (руке´, о руке´); сту´
...Безударные гласные в падежных окончаниях...
...;, ектения´ — в ектении´, бытие´ — о бытии´, житие´ — о житии´, в житии´, но: остриё — на острие´, об острие´, Зия´, Алия´, Зульфия´ (личные имена) — о Зие´, об Алие´, к Зульфие´, Кызыл-Кия...