As the OP has not provided a definition of "bug-eyed monster", we will go with the OED definition of "bug-eyed":
Having bulging eyes; esp. in phr. bug-eyed monster, an extra-terrestrial monster with bulging eyes; abbrev. B.E.M.
So we are looking for early instances of extra-terrestrial monsters with bulging eyes.
Apparently it was the cover of the June 1939 Thrilling Wonder Stories that inspired the coinage of the phrase "bug-eyed monster" in a letter by Martin Alger in the next issue (Thrilling Wonder Stories, August 1939), according to the Historical Dictionary of Science Fiction. Alger wrote (see p. 121, column 2 at the Internet Archive):
Speaking of The SPWSSTFM, the cover inspired me to organize the SFTPOBEMOTCOSFP. (Society For The Prevention Of Bug-Eyed Monsters On The Covers Of Science-Fiction Publications.) Yours for complete novels and more civilized covers.
(By the way, the "SPWSSTFM" that Alger mentions is the Society for the Prevention of Wire Staples in ScienTiFiction Magazines, or something like that.)
Of course 1939 is nowhere near the beginning of BEMS in science fiction. As my answer to the question, I propose three covers from the first year of Amazing Stories, namely, Vol. 1, No. 2, May 1926, Vol. 1, No. 4, July, 1926, and Vol. 1, No. 7, October, 1926, all by the artist Frank R. Paul.
This is just a starting point for further research; no doubt earlier examples will be found. A commenter has suggested The War of the Worlds (1897) by H. G. Wells, but I have doubts about that: Wells describes his Martians as having "large dark-coloured eyes", but I'm not sure they are especially bulgy.