tl;dr:
- 1979 as the title of a published work.
- 1854 as a reference in general.
- Usage peaked in the 1990s through 2010s.
1979: The Life—and Lies—of Maud Gonne
was an essay published by Conrad Balliet in Ireland.
The reference comes in Volume 6 (although I am not sure which number) of "Biography: An Interdisciplinary Quarterly" that has been published since 1978 by the University of Hawai'i Press.
Each issue also offers insightful reviews, concise excerpts of reviews published elsewhere, an annual bibliography of works about biography, and listings of upcoming events, calls for papers, and news from the field.
1854 reference
As mentioned in the comments the phrase certainly dates much further back than this. The line is used to describe P.T. Barnum's autobiography The Life of P.T. Barnum: Written by Himself in the Portland Transcript in 1854.
Here we have a revelation of the life and lies of the great showman, or as much of them as he chooses to reveal.
1990s to 2010s Trend
Although the trend does seem to be much more recent, perhaps starting in the 1990s (shortly after your first find of The Life and Lies of Bertolt Brecht in 1994) and surging in the late 2000s and 2010s (coinciding with the Harry Potter novels and films). At least according to this Google Ngram...