Like many readers, I was enraptured by the maps in J. R. R. Tolkien's The Lord of the Rings (1954-55) and The Hobbit (1937). After their 1965 reprinting in a widespread American edition, maps became more common in works of science fiction and fantasy. I particularly enjoyed the maps of an imaginary kingdom in Lloyd Alexander's Prydain Chronicles(1964-68) and star charts in Cherryh's Chanur series(1982-92).
I think it would be worthwhile to split this question into science fiction and fantasy genres, as these genres have often taken separate paths in literature. I am not sure whether to classify Jonathan Swift's Gulliver's Travels (1726) as science fiction or as fantasy. This is certainly an early example of speculative fiction illustrated with maps, but I would be more satisfied to find the earliest use of a map in the forebears to the modern genre of fantasy, as it might have influenced later authors.
To sum up: What was the earliest printed map in the fantasy genre? (That is, not merely the earliest map to be mentioned in a text.)