O.E. beleogan "to deceive by lies," from be- + lie (v.1) "to lie, tell lies." Current sense of "to contradict as a lie" is first recorded 1640s. The other verb lie once also had a formation like this, from O.E. belicgan, which meant "to encompass, beleaguer,"
and in M.E. was a euphemism for "to have sex with" (i.e. "to lie with carnally").