(1) This is a very interesting question. Actually, I could answer you straight away that the question does not start because the Rambam Hilchos Isurei Bi'ah 18:3 Paskens our Gemara in the following way: " A Nochri, slave, Nasin, Mamzer, Amonite or Moabite Ger, or 1st or 2nd generation Adomi or Mitzri Ger, or someone with a deformity in his reproductive organs (i.e. Petzu'a Dacha or Krus Shafchah) or a Chalal who had relations with a Jewish woman, renders her a "Zonah" and disqualifies her from marrying a Kohen."

So according to the Rambam these cases in the Gemara do not make her into a Chalalah, but rather into a Zonah, so your question from 77b does not get off the ground because a Zonah does not only have to be from a Psul Kehunah.

(2) I could also reject your Ta'anah form the fact that the Gemara here learns this form Kohen Gadol and Almanah that this suggests the Psul must be Chalalah. I would argue that the Gemara is not deriving from K.G and Almanah that the Psul must be specifically Chalalah. Rather, I would say that the Limud is that just as a K.G. renders the Almanah invalid to a Kohen, so all the case in our Gemara make her invalid to a Kohen, but not necessarily a Chalalah.

You are forced to say something on the lines of the above to explain the Rambam's Shitah, because the Rambam calls her a Zonah, even though the Gemara learns it from K.G. and Almanah, so it must be that we are not deriving from there that she specifically becomes a Chalalah.

(3) However the problem is that Rashi Sanhedrin end 69a DH Ba explains the Gemara there "If one of the Pesulim had relations with her this disqualifies her from marrying a Kohen" to mean "for instance a Kusi, Chalal, Nasin or Mamzer rendered her a Chalalah and invalidates her". So Rashi does say that he made her a Chalalah and your question becomes a very strong one:- how can he make her a Chalalah, surely these invalid people are not only invalid for Kohanim?!

(4) And now that we have seen Rashi in Sanhedrin it makes it easier for us to notice something that Rashi here 75a DH m'Kohen wrote. He explains that the Limud from K.G. to Almanah is because he was "Mechalel her with his Bi'ah". Rashi seems to hint at the fact that he made her a Chalalah which suggests that we are deriving from here that the other Pesulim also make a Chalalah. This is exactly what you are arguing so your question from 77b becomes very powerful - a Chalalah is only created by a Psul of Kehunah?!

(5) Before I try to make things better I will make them worse by citing 2 statements of Rashi in Yevamos which seem consistent with what he writes here and in Sanhedrin. See Rashi Sanhedrin 57a DH Ho'il that if a Kohen was married and then became a Petzu'a Dacha and had relations with his wife, he renders her a Chalalah. Rashi seems to say that even though a Petzu'a dacha is forbidden to marry anyone of the Kehal Hash-m, and is not only a Psul Kehunah, nevertheless, he makes her a Chalalah.

(6) See also Rashi Yevamos 70a in the Mishnah DH Nesheihem who also writes that a Petzu'a dacha or Krus Shafchah makes his wife a Chalalah. The Rashba there writes that Rashi's explanation is not clear because a Chalalah only comes from Isurei Kehunah. The Meiri there also writes that Rashi wrote this comment "Agav Shitfei" - "out of speed", but in fact he makes her a Zonah as Tosfos explains.

(7) However I will cite the explanation of the Aruch l'Ner Yevamos 70a to attempt to resolve the difficulty in Rashi, and I will close on this note. He explains on the basis of Tosfos Yevamos 44b end DH Hacha who writes that the reason a Zonah is disqualified from eating Terumah is because the Torah (Vayikra 21:7) mentioned Zonah together with Chalalah. Just like a Chalalah is prohibited for Terumah, so is a Zonah. When Rashi writes that the forbidden relationship made her a Chalalah, this really means it made her into a Zonah, but since a Zonah has the same din for Terumah as a Chalalah, Rashi wrote Chalalah.

(8) Aruch l'Ner gives an addition suggestion why Rashi always seems to mention Chalalah. This is because even though the first Bi'ah makes her a Zonah nevertheless if the Kohen has a further Bi'ah this automatically makes her into a Chalalah, as the Gemara states (Kidushin end 77b) that if a Kohen had relations with his sister this makes her a Zonah but the second time it makes her a Chalalah. Since the women made invalid by the Psul people mentioned at bottom 74b will become Chalalos if they live with a Kohen, therefore Rashi refers to them as Chalalah immediately.

Thank you very much for your interesting question which has opened up a fascinating Sugya

Shavu'a Tov

Dovid Bloom