The Mishna in Sanhedrin 9:4 says that one can be obligated in a more severe death penalty for a second offence that occurred after being sentenced to a less severe death penalty for a different action.
מִי שֶׁנִּתְחַיֵּב בִּשְׁתֵּי מִיתוֹת בֵּית דִּין, נִדּוֹן
בַּחֲמוּרָה. עָבַר עֲבֵרָה שֶׁנִּתְחַיֵּב בָּהּ שְׁתֵּי מִיתוֹת,
נִדּוֹן בַּחֲמוּרָה. רַבִּי יוֹסֵי אוֹמֵר, נִדּוֹן בַּזִקָּה
הָרִאשׁוֹנָה שֶׁבָּאָה עָלָיו:
He who incurs two death penalties imposed by the court is executed by
the severer. If he committed one sin for which a twofold death penalty
is incurred, he is executed by the severer. R. Jose says: “He is
judged according to the first penalty which was placed upon him.”
The Bartenura explains that the case of "He who incurs two death penalties" as one who transgresses a lighter capital offense and is convicted and sentenced, and goes ahead and transgresses a more severe capital offense:
כגון שעבר עבירה קלה ונגמר דינו לעבירה קלה, וחזר ועבר עבירה חמורה,
סלקא דעתך אמינא כיון דנגמר דינו לעבירה קלה, האי גברא קטילא הוא, קמשמע לן
This is also how the Rambam explains the Mishna:
מי שנתחייב בשתי מיתות ב"ד נדון בחמורה עבר כו': דברי הראשון באדם שעבר
עברה ונגמר דינו למיתה קלה ואח"כ עבר עברה חמורה סלקא דעתך שיהא נדון
בקלה לפי שהוא גברא קטילא ולא ישגיחו למה שעשה אח"כ קמ"ל שהוא נדון
This is based on Rava's explanation of the Mishna in Sanhedrin 81a:
אמר רבא הכא במאי עסקינן כגון שעבר עבירה קלה ונגמר דינו על עבירה קלה
וחזר ועבר עבירה חמורה סלקא דעתא אמינא כיון דנגמר דינו לעבירה קלה האי
גברא קטילא הוא קמ"ל
Rava says: With what are we dealing here? We are dealing with a case
where he violated a relatively minor transgression punishable by a
less severe form of execution, and his verdict was issued for the
minor transgression, and he then violated a major transgression
punishable by a more severe form of execution. It could enter your
mind to say: Once his verdict was finalized for the minor
transgression, the legal status of this individual is that of a dead
man, and anything that he does thereafter is insignificant. To counter
this, the tanna teaches us that he is liable to be punished for the
subsequent transgression, and if it is punishable by a more severe
form of execution, he is executed with that form of execution.
So to directly address your questions: yes, he is liable for the murders. However, since the punishment for murder isn't the most severe punishment (stoning and burning are considered more severe), then the question may not always be applicable (i.e. if he was sentenced to stoning for his previous crime, that is already the most severe death penalty and can't be topped).
Of course (and H/T to Heshy for mentioning it), this is only referring to the physical punishment that Bais Din is required to mete out, since corporeal beings can not receive more than a single death sentence. Hashem is just and can ensure that every action that a person does is properly rewarded or punished according to His justice.