When regarding the etymology of both verbs there are interesting findings:
kehren Vb. 'fegen'. Das nur westgerm. bezeugte Verb ahd. kerien, kerren (8. Jh.), mhd. kern, mnd. mnl. kēren, nl. keren setzt germ. karjan voraus. Das zugehörige Grundwort dürfte in ahd. ubarkara 'Unreinigkeit, Unflat' (10./11. Jh.), isl. kar 'Schmutz' erhalten sein.DWDS
This means that despite its usage in the south "kehren" has a common root in Niederdeutsch.
fegen Vb. 'mit dem Besen reinigen, kehren', südd. 'naß reinigen, wischen' ahd. fegōn 'säubern, putzen' (10. Jh.), mhd. vegen 'kehren, reinigen, putzen', asächs. fegon, mnd. vēgen, mnl. vēghen, nl. vegen, ablautend mnl. vāghen, nl. (weg)vagen, anord. fāga 'reinigen, glänzend machen, schmücken' sowie die unter fair (s. d.) genannten germ. Formen können mit lit. puõšti 'schmücken, putzen', lett. post 'schmücken' auf eine Wurzel ie. pek̑- 'hübsch machen, aufgeräumt oder vergnügt sein' zurückgeführt werden [...]DWDS
Taken this into account "fegen" may have much older Indo-European roots, and is etymologically related to the English adjective "fair".