For hundreds of years, in English and no doubt in other languages, flies have been cited metaphorically in connection with the idea of enjoying unseen intimacy or intelligence. Thus for example, in Romeo and Juliet (by 1595) we have this (in an 1821 edition):
Romeo. Tis torture, and not mercy: heaven is here,/ Where Juliet lives ; and every cat and dog,/ And little mouse, every unworthy thing,/ Live here in heaven, and may look on her,/ But Romeo may not.—More validity,/ More honourable state, more courtship lives/ In carrion flies, than Romeo: they may seize/ On the white wonder of dear Juliet's hand/ And steal immortal blessings from her lips;/ Who even in pure and vestal modesty,/ Still blush, as thinking their own kisses sin;/ But Romeo may not; he is banished:/ Flies may do this, when I from this must fly;/ They are free men, but I am banished.
Romeo's speech is invoked (and rewritten) by Litchfield Moseley, "A Successful Elopement," in Once a Week (September 3. 1870) as part of a lover's letter to his beloved:
"Oh! Clementina, although only two days, it seems quite an age since I have seen you. As Romeo says:— 'Flies may gaze on thee; would I were a fly,/On gauzy wing I to my Clem would hie,/ And gaze, and gaze till I wore out mine eye.'"
Also (and more specifically relevant to the modern sense of "a fly on the wall"), in Susanna Centlivre, Marplot in Lisbon (1711), reprinted in The Works of the Celebrated Mrs. Centlivre, volume 2 (1761):
Marplot. Then hang Honour, I say, 'tis good for nothing but to spoil Conversation. Shall I beg a Pinch of your Snuff, Colonel?
Enter Colonel Ravelin's Servant with a Letter.
Ravelin. With all my heart. [Gives him his Box.
Marplot. A Letter! Wou'd I were a Fly now, that I might swop down upon the Paper and read it before his Face : Lord, Lord, what wou'd I give for an universal Knowledge! [Aside.
And from James Parry, The True Anti-Pamela: or, Memoirs of Mr. James Parry (1741):
To Mr. Parry.
I would have given the World (were it mine) that I had staid home yesterday. Good God, what can Mrs. J—s, who is a perfect Stranger to me, think of either of us. I was very much surprised to see you in such a Passion after all the Protestations to the contrary, that you made me here last Saturday Night. If you loved me as you say you do, you would hardly affront me. As Mrs. J—s knows all, I'll take her Advice, and only hers in every Thing. Let me know next Post if you'll let me have the Money, or no : Else I must go soon to Ross to fetch some of my own, for I can't be here without any. My sincere Love and Service to Mrs. J—s, (for I find you are there still.) So now Adieu.
I wish I were a fly, to see if you shew this to any one. I must, I find, take Care how I write, since I am threatned by you ; it was once otherwise. I han't Time to say any more at present, or I'd scold you.
Also relevant is this translation (by 1898) of Balzac's Letters of Two Brides (1840):
All this, dear Mme. de l'Estorade, happened a fortnight ago, and it is a fortnight now since I have seen the man who loves me, for that he loves me there is not a doubt. What is he about? If only I were a fly, or a mouse, or a sparrow! I want to see him alone, myself unseen in his house.
I haven't been able to determine when this novel was first translated into English, but clearly Balzac has in mind a fly-on-the-wall (or mouse-in-the-corner or sparrow-at-the-window) scenario of exactly the kind that our modern idiom describes.
The earliest match in a Google Books search for the exact words "a fly on the wall" in the intended idiomatic sense is from Julia Cecilia Stretton, Woman's Devotion (1855), a three-volume novel published in London:
Had Lady Jane been a fly on the wall, and seen Frank's delighted face ; how he tried to catch a glimpse of the crimson cheek, hidden in his bosom ; how he said, " Say that again, my wife, and I will go to York to-morrow, and try to do my duty, and I won't care for any scoff or scorn. And how nest said it in a fairy-like whisper, and how he declared, though he looked delighted and kissed her little hand over and over again, that h did not hear her, and that she must say it louder, (wicked, exacting young fibbing husband), and how she had to say it, and a great deal more, over and over again—if, as I said, Lady Jane had been a fly on the wall, and beheld this scene, she would have thrown up her beautiful aristocratic nose, and said, "Foolish children, bring them their pinafores, and bread and milk."
The next match in Google Books is from 1880, followed by three matches from about the turn of the 20th century. From Adeline Dutton Train Whitney (an American author), Odd or Even? (1880), which uses the phrase four times in the course of about ten pages:
But "things ain't never as you count on," Mother Pemble said to herself. "[Deacon Ambrose]'s got that ninety-nine year an' six days so set in his mind that he'll slip up in one of the seventies yet, while he's lookin' forrud to it. An' if there ain't a cretur surprised, there never was one. I 'd like to be a fly on the wall, in t' other world, to see him come in! "
All the flies in Egypt could not have been in all the places where Mother Pemble had wished herself " on the wall " in that wise.
Meanwhile, she was, as a fly on the wall, in the "east settin'-room," with the big "seckerterry," against the opposite wall, or rather against the door in the front passage of the house, which she would have closed in that way when she first took to her bed and her imprisonment here.
"What'v I got to dip with, Mother Pemble?"
"O, I d'know, yer turnin' things over all the time, an' ye ain't bound to nobody. Care'line, she ain't got the curiosity of a miskeeter. Not half," she emended, as the excess of her illustration occurred to her. "I'd like to be a fly on the wall up there over that old seckerterry."
"T'aint the age o' merricles; 'n yit ther might be sech a thing 's 't I sh'd be aout n' abaout, f'r all, afore I die. 'F I ain't, I will be after, 'f ye don't keep things straight an' above-board, Ambrose Newell,—'n I go fust. That I tell ye."
"Ye'd like to be a fly on the wall, wouldn't ye?" retorted the deacon, rising up and rolling forward the secretary front again, and turning the key, shutting and locking the deep drawer also, as he folded back the desk-lid. "Ye'd buzz, wouldn't ye? Well, I should n't kind o' wonder ef 't was what ye would be, 'f the Lord saves all the pieces, an makes the most he can out o 'm."
From Lucy Hill, Marion's Year in a German School (1899):
I was immediately surrounded, and in a tone just loud enough to be distinctly heard Gretchen Später, our pet, said: "Girl, I knew that would come. Would that I were a fly on the wall that I might hear the lecture she [Marion Garland] will get! Every one of us knows what it means to be summoned to the private reception room. She has come to the right place if she wishes to make any thing of herself. We shall not recognize her a year from now, but I pity her while she is undergoing the transformation."
I couldn't find much information online about Lucy Ann Hill, other than the fact that she also wrote a fictionalized travel book in 1879 called Rhine Roamings, but both her books appear in the "Cairns Collection of American Women Writers." The novel is about an English girl who has spent much of her childhood in the United States and is now attending school for a year somewhere in Germany.
From Bithia Mary Croker ("a prolific Anglo-Indian author," according to Wikipedia), The Happy Valley (1904):
"Rachel, how can you laugh? I've never had such an experience. Imagine his daring to propose to me! Can you grasp such—such—audacity?"
(To realize Mr. Clegg's audacity required no mental effort on my part.)
"What sensational stories he will tell Lady G.!" I exclaimed. "I wish I were a fly on the wall."
"Yes, but he won't have it all his own way. Captain Branksome knows Sir Robert ; he is going down there to-morrow morning to thresh out this scandal and to bring Mr. Clegg to book."
From Bettina von Hutton (another American novelist), The Halo (1907):
"Something queer of all this he [the cabby] meditated; "that lean chap didn't look quite right, an' she 'adn't no patience with 'im neither. Then in she goes to the old 'ouse, an' then along comes another 'ansom with the lean chap. Then I waits an hour, an' out she comes with the little kids, kissin' 'em, an' the biggest little kid arsks 'er 'er nime! If she didn't know 'im, why did she kiss 'im? An' before we'd got to the corner out comes the lean 'un, lookin' like a bloomin' corpse. Something must 'ave 'appened in that old 'ouse, an' I'll keep a lookout in the People and see wot it was. I'd like to 'ave been a fly on the wall during that there interview, I would. A fly on the wall with a tiste for short'and."
So we have five instances of "a fly on the wall" used in the modern idiomatic sense in the space of 52 years, all in novels by female writers—the first English, the next American, the third probably American but with a special interest in Germany, the fourth Anglo-Indian (but living in England when she wrote her book), and the fifth American. This is not an especially random-looking group of sources.
Thereafter, Google Books finds matches from 1915, 1916, and 1930, and then seven unique instances during the period from 1945 through1947.
Whether Julia Stretton is directly responsible for popularizing the notion of being "a fly on the wall" in order to gather information or witness a private scene is difficult to determine; but it seems fair to say that the six English and American women cited above whose relevant novels appeared between 1855 and 1907 almost certainly deserve credit for popularizing (in English) that wording for a very old idea.