Old English beleogan "to deceive by lies," from be- + lie (v.1) "to lie, tell lies." Current sense of "to contradict as a lie, give the lie to, show to be false" is first recorded 1640s.
The other verb lie once also had an identical variant form, from Old English belicgan, which meant "to encompass, beleaguer," and in Middle English was a euphemism for "to have sex with" (i.e. "to lie with carnally").