Magnus, Earl of Northumberland, was so called not from his red or bloody hand, but on account of his long red beard or mane. He was slain in the battle of Sark (1449).
He was remarkable for his long red beard, and was therefore called by the English Magnus Red-beard; but the Scotch in derision called him `Magnus with the Red Mane.
—Godscroft, fol. 178.
Source: Dictionary of Phrase and Fable, E. Cobham Brewer, 1894
More on Redmain from Infoplease: