One of the problems that this raises is the exact nature of justice.
In some parts of the real world, for instance, it is considered just to sentence a man to a long prison term for defending his property with lethal force (against burglars on their third or fourth burgalry of his property). In others, it is considered honorable for a man to kill a female relative for being raped. And it would not be considered just to punish that man. Now, IRL, I don't consider either example to really be just (laying my objectivist credentials on the table). However, the point is that both of those societies use the term justice to refer to two somewhat different codes. Justice seems to be very widely acknowledged (maybe universally) as a virtue--although it is defined somewhat differently.
So, if you are going to portray two different gods or two different religions (good and evil versions of the same religion would probably qualify for this--as would Lawful and Chaotic if anyone can come up with a coherent and useful deliniation of such terms), it would probably make sense for the "Justice vs. Mercy" debate to be framed as "Justice vs. Justice" by its participants.
It's quite significant that, in The Sigil's parable resolving the conflict between justice and mercy, both the concept of justice and the concept of mercy actually come from the same religion. It might not have worked so well if the allegory were changed to describe a non-Christian conception of justice.
Mercy, on the other hand, is not nearly so widely acknowledged as a virtue. (Indeed, IIRC, mercy or something like it appeared on one of Aristotle's lists of vices!) Shakespeare's famous appeal to mercy in The Merchant of Venice would probably not make sense to people from many of the worlds' historic cultures. Among peoples whose cultures are shaped by a valuation of mercy, their conception of justice is also shaped by that valuation.
If you chose to have both religions value both justice and mercy, you could take jrogbrowning's suggestion and give them different concepts of mercy. Even if you don't, however, there could still be room for dramatic differences between the religions based on their metaphysical outlooks. One could value both justice and mercy and still maintain a class of people as chattel for no other reason than their birth if one believes in the reincarnation or the transmigration of souls. In that case, their status could be just because they earned it in a previous incarnation. Similarly, tampering with their subjegation and oppression would be unmerciful because it interfered with the growth process that enabled the oppressed individuals to earn a better incarnation. Or a society could believe that people who die after a certain age will rise as undead and have their souls tormented for all eternity. Consequently, it would be just and merciful for them to kill everyone who reached that age in some rite dedicated to ensuring the proper passage of their souls. To people who didn't share the metaphysical beliefs, such practices would seem both unjust and unmerciful but those who did share those beliefs about the world could call them just and merciful by exactly the same standards. (And in a fantasy world, they could even be right. (And, in the case of the undeath, it could be the result of an ancient curse that the PCs could reverse--something that could potentially lead to dramatic upheaval in the culture)).
So, instead of having one religion that values "justice" and another that valued "mercy", it might be better to have two religions which valued "justice" but which have different concepts of justice. And one of them might have their concept of justice informed by a valuation of mercy while the other doesn't.
Alternately, you could create the conflict by ascribing different metaphysical beliefs to religions that share the same concepts of justice and mercy.
