I answered this question before by suggesting that a Kal va'Chomer, which is a d'Oraisa way of learning (as it is the first of the Thirteen Midos sheha'Torah Nidreshes ba'Hen, as we recite each morning at the beginning of Shacharis), can be stronger than the Mekor that the Gemara has.
I have now found a support for this from Tosfos in Zevachim 10b (DH u'Mah Olah), who says that a Kal va'Chomer can come and override a Hekesh. I suggest that in the Gemara here in Makos 5b, the Kal va'Chomer could also have overriden the Mekor of the Gemara that they do not get killed if there was a G'mar Din.
Kesivah v'Chasimah Tovah,
Dovid Bloom
I found another support for the above idea, about how strong a Kal va'Chomer can be.
1) Rashi in Sanhedrin 73a (DH Hekesha) writes that a Hekesh or a "vacant" Gezeirah Shavah are considered as equivalent to being written explicitly in the Torah, and consequently a punishment can be given based on such a Gezeirah Shavah or Hekesh. In contrast, one cannot give a punishment based on a Kal va'Chomer, because a person can expound a Kal va'Chomer on his own, even if he has not heard it from his teacher; therefore, a Kal va'Chomer cannot be considered as being explicit in the Torah. Rashi in Sanhedrin 51a (DH Asya Heinah) writes something similar about the difference between a Gezeirah Shavah and a Kal va'Chomer.
2) However, the above statements of Rashi clearly apply only according to the opinion that "Ein Onshin Min ha'Din," that we cannot give a punishment based on a Kal va'Chomer. However, there is an opinion in the Gemara that disagrees and maintains "Onshin Min ha'Din," that we can administer a punishment based on a Kal va'Chomer. (This is the opinion of Rebbi Yitzchak; see Kerisus, beginning of 3a; see also Tosfos to Bava Kama 4b, DH v'Edim, who writes that for monetary matters we can punish based on a Kal va'Chomer. Tosfos implies that the Gemara here in Makos maintains "Ein Onshin Min ha'Din" only because it discusses capital punishment. However, Rebbi Yitzchak in Kerisus 3a maintains that capital punishment also may be administered based on a Kal va'Chomer.)
3) My argument now is that the opinion that maintains "Onshin Min ha'Din" even for capital punishment must hold, according to Rashi in Sanhedrin 51a and 73a, that a Kal va'Chomer is also considered as being written explicitly in the Torah.
4) Now, back to our Gemara in Makos 5b: When the father of Berebi said to his son that it is a Kal va'Chomer that if they killed then they also get killed, he must be following the opinion of Rebbi Yitzchak in Kerisus 3a that "Onshin Min ha'Din." Even though Berebi said to his father that he had taught them that "Ein Onshin Min ha'Din," Berebi's father was aware that there is a dispute about this, and when he asked the question to his son at the beginning of the Sugya, he was following the opinion "Onshin Min ha'Din." As we have shown, according to this opinion a Kal va'Chomer is considered as being written explicitly in the Torah. If so, the Kal va'Chomer has the power to override the Mekor that if they have already killed they do not get killed.
Dovid Bloom