The Oxford English Dictionary - which invariably tries to establish the earliest use of words and phrases - credits it to Churchill in a speech to the House of Commons delivered on 22nd February 1906.
Doubtless cunning Churchill wanted to say 'lie' and 'liar' but knew he'd be using unparliamentary language of an opponent and would be asked by the Speaker to withdraw the statement. That would explain this euphemistic circumlocution being first found recorded in Parliament.
Apparently, Fred, the speech was about contracts offered to Chinese workers in South Africa and Churchill said these might not be proper. However they could not be classified as slavery "without some risk of terminological inexactitude". So, it seems it wasn't an accusation of some other MP's lying so much as a reference to an exaggeration in describing a work-situation.