c. 1200, pilegrim, "a person traveling to a holy place (as a penance or to discharge some vow or religious obligation, or seeking some miracle or spiritual benefit)," also "a traveler" generally, "a wayfarer," from Old French pelerin, peregrin "pilgrim, crusader; foreigner, stranger" (11c., Modern French pèlerin), from Late Latin pelegrinus, a dissimilation of Latin peregrinus "foreigner, stranger, foreign resident" (source of Italian pellegrino, Spanish peregrino, GermanPilger), from peregre (adv.) "from abroad," from per- "beyond" + agri, locative case of ager "country, land" (from PIE root *agro- "field").
The change of the first -r- to -l- in most Romance languages is by dissimilation; the -m appears to be a Germanic modification. Pilgrim Fathers "English Separatists who crossed the Atlantic on the Mayflower and founded Plymouth colony in Massachusetts in 1620" is attested by 1799. They sometimes wrote of themselves as Pilgrims from c. 1630, in reference to Hebrews xi.13. Pilgrim in U.S. Western slang for "an original settler" is by 1841, later "a newcomer, 'tenderfoot,'" perhaps originally in reference to the Mormon migrations.