"intense and painful regret due to a consciousness of guilt; the pain of a guilty conscience; deep regret with self condemnation," late 14c., from Old French remors (Modern French remords), from Medieval Latin remorsum"a biting back or in return," noun use of neuter past participle of Latin remordere "to vex, torment disturb," literally "to bite back, bite again" (but seldom used in the literal sense), from re- "back, again" (see re-) + mordēre "to bite," which is perhaps from an extended form of PIE root *mer- "to rub away, harm."
The sense evolution was via the Medieval Latin phrase remorsus conscientiæ ("remorse of the conscience," translated into Middle English as ayenbite of inwit). Middle English also had a verb, remord "to strike with remorse, touch with compassion, prick one's conscience."