The origin of the word is obscure, but OED (Second Edition, 1989), MED and DMLBS all suggest a possible Anglo-Norman origin, associating the word with chevaler1. The earliest attestations are found in Latin sources (1317).
s.
1robber, brigand on horseback mainly active near the Scottish border:
(
1324
)
en la primere flote passassent hobelours, shavaldours et archiers et autres gentz suspeccionous
66
(
1343-50; MS: 1343-50
)
les Escoces entrerent en Engeltere, et robberent en Northumberland, et firent un shivaldour, William Waleis, lour cheventein
25
(
1355-64; MS: s.xivex
)
En quel houre, Johan le Irroys ravist la Dame de Clifforde. Lez maufesurs estoint appellez schavaldours
84
shavaldour (1324)