Mishna in Makoth 2:7
וְכֹהֵן גָּדוֹל שֶׁהָרַג , אֵינוֹ יוֹצֵא מִשָּׁם לְעוֹלָם
A Cohen Gadol who kills goes to the Ir Miklat forever.
They would have to appoint another one, to do the Avoda on Yom Kippour, as the first one loses his job as Kohen Gadol, as the Rambam הלכות רוצח ושמירת נפש at (7:14) says about all those sentenced to Ir Miklat, after they can go home:
אַף עַל פִּי שֶׁנִּתְכַּפֵּר לוֹ אֵינוֹ חוֹזֵר לַשְּׂרָרָה שֶׁהָיָה בָּהּ לְעוֹלָם. אֶלָּא הֲרֵי הוּא מוּרָד מִגְּדֻלָּתוֹ כָּל יָמָיו הוֹאִיל וּבָאָה תַּקָּלָה זוֹ הַגְּדוֹלָה עַל יָדוֹ:
The Rambam in הלכות רוצח ושמירת נפש at (7:10) actually says that this "eternal sentence" is only if there was no another Cohen Gadol appointed at the same time.
וְכֹהֵן גָּדוֹל שֶׁהָרַג וְלֹא הָיָה שָׁם כֹּהֵן גָּדוֹל אַחֵר. הֲרֵי אֵלּוּ גּוֹלִין וְאֵינָן יוֹצְאִין מֵעִיר מִקְלָט לְעוֹלָם
If the Cohen Gadol co-existed with another Cohen Gadol (e.g. one of them was incapable of serving for Yom Kippour so they appointed a second one) then the murderer would get out when the other one died. But he would not get his job back, as above.