1550s, "mildness or gentleness shown in exercise of authority," from Latin clementia "calmness, gentleness," from clemens "calm, mild," related to clinare "to lean," often said to be from PIE root *klei- "to lean" + participial suffix -menos (also in alumnus). For sense evolution, compare inclined in secondary meaning "disposed favorably." But de Vaan is dubious on phonological grounds.
Clemency is exercised only toward offenders, being especially the attribute of those in exalted places having power to remit or lighten penalty. [Century Dictionary]
Earlier in same sense was clemence (late 15c.). Meaning "mildness of weather or climate" is 1660s (a sense also in Latin); clement (adj.) is older in both senses (late 15c. and 1620s respectively) but now is used only in negation and only of the weather.