The purely formal answer seems to be The Legend of Zelda (1986), with further examples in later instalments of the series; but with honourable mentions to Ultima V (1988) where you ride down a waterfall to the underworld, and Ultima III (1983) and IV (1985) where you go into whirlpools to reach otherwise inaccessible locations.

But even in the 1980s it felt like a traditional thing. I remember being surprised, playing Zork back in the day, that it wasn't possible to go through the waterfall to reach a cave. So where did that sense of familiarity come from? Part of the answer is that caves behind waterfalls are a thing you can find in the real world. But the idea also has a very strong heritage in fiction in other media.

I'd be willing to bet that most western examples in the last several decades can be traced back to the Tintin book Prisoners of the Sun (1949, originally serialised 1946-1948), which has a famous scene where Tintin falls into a waterfall, then he calls for help, and Captain Haddock throws him a rock tied to a rope so that he and another companion can climb along the rope, through the water, to get to him. Certainly not all examples are based on that -- there's one in The Lord of the Rings (The Two Towers, book 4, ch. 6, 1954) which comes from somewhere else -- and I can't begin to guess at the inspiration for the ones in Zelda. The Phantom (1936 onwards) also features a cave hidden by a waterfall, but IIRC you don't have to go through the water to get to it.

The earliest seminal examples seem to be, for modern western literature, the cave that Grettir hides in in Grettir's saga (13th/14th century); and in the east, Shuilian cave ("water-curtain cave") in Journey to the West (16th century). Either or neither might be inspired by a real-life example.

In the case of Grettir's saga we may be able to push the motif even further back to Beowulf (7th-8th century??), lines 1495-1516, where Beowulf dives to the bottom of a lake, and is snatched by Grendel's mother, who drags him to an underwater cave . The scene has been interpreted as another cave behind a waterfall, but that's probably under the influence of Grettir's saga. Klaeber's commentary on the passage has this to say:

Grendel's dam, aroused by a stranger's appearance in the water, goes to the bottom of the lake (to which Bēowulf had plunged, like Grettir, "in order to avoid the whirlpool and thus get up underneath the waterfall," Lawrence, l.c. 237) and drags him to her cave. ...In the Grettissaga the hero straightway enters the cave to fight the monster; in the Samsonssaga the hero is seized by the troll-woman in the water and dragged by her to the bottom. This dual conception, probably, is responsible for the lack of clearness in Beowulf.

(For the record, the text doesn't look at all unclear to me; it seems more like scholars are trying to read things into it that aren't there.)

Tolkien's waterfall, I think we can safely say, comes from Grettir. Zelda, I don't know: it might be inspired by Journey to the West but I can also imagine Tintin as an inspiration. Hergé's inspiration for Prisoners of the Sun is even less clear: I can imagine him being familiar with both Grettir's saga and Journey to the West, but I can also imagine him knowing a real-life example.

Edit. Given that this thread had basically been buried when I posted this reply, I'm a tad surprised to see it blow up like this. Oh well!

/u/Snowbirdy below has pointed out an earlier game example in MUD1 (1978). I never played this and I can't find the game's layout documented anywhere, but it certainly sounds plausible even if I can't verify it.

For literary precursors, Zane Grey's Riders of the Purple Sage (1912) suggested by /u/pappyjack is right on the money. Here's the description of the cave entrance, from chapter 5:

All this Venters noted in one glance. After that he watched with a thrilling eagerness. Straight at the waterfall the rustlers drove the burros, and straight through the middle, where the water spread into a fleecy, thin film like dissolving smoke. Following closely, the rustlers rode into this white mist, showing in bold black relief for an instant, and then they vanished.

Venters drew a full breath that rushed out in brief and sudden utterance.

"Good Heaven! Of all the holes for a rustler!... There's a cavern under that waterfall, and a passageway leading out to a canyon beyond. Oldring hides in there. ..."

I'm not totally convinced by some of the other examples that have been mentioned. I was aware of the one in the film of The Last of the Mohicans, but I'm not persuaded by /u/SweetMister's quotations from the book. I was ignorant of the one in Tom Sawyer (1876), suggested by /u/Thoguth, and it's definitely worth noting -- but the text makes it clear that the waterfall is only a trickle, and it's not the waterfall that's concealing the passage but a curtain of limestone created by the trickle over the ages. Here's what Mark Twain writes:

Presently [Tom and Becky] came to a place where a little stream of water, trickling over a ledge and carrying a limestone sediment with it, had, in the slow-dragging ages, formed a laced and ruffled Niagara in gleaming and imperishable stone. Tom squeezed his small body behind it in order to illuminate it for Becky's gratification. He found that it curtained a sort of steep natural stairway which was enclosed between narrow walls, and at once the ambition to be a discoverer seized him.

So, not bad; and the cave itself is certainly influential and iconic; but I'm not so sure that the bit about the waterfall is quite so influential.

Finally, for the sake of completeness, here's the description in Grettir's saga, chapter 66:

Síðan hljóp hann af bjarginu og niður í fossinn. Sá prestur í iljar honum og vissi síðan aldrei hvað af honum varð. Grettir kafaði undir fossinn og var það torvelt því að iða var mikil og varð hann allt til grunns að kafa áður en hann kæmist upp undir fossinn. Þar var forberg mikið og komst hann inn þar upp á. Þar var hellir mikill undir fossinum og féll áin fram af berginu. Hann gekk þá inn í hellinn og var þar eldur mikill á bröndum. Grettir sá að þar lá jötunn ógurlega mikill. Hann var hræðilegur að sjá.

[Grettir] jumped from a rock and got down to the fall. The priest saw the soles of his feet but after that did not know what had become of him. Grettir dived beneath the fall. It was very difficult swimming because of the currents, and he had to dive to the bottom to get behind the fall. There was a rock where he came up, and a great cave under the fall in front of which the water poured. He went into the cave, where there was a large fire burning and a horrible great giant most fearful to behold sitting before it.

Shout-out to /u/Abide_Dude for an excellent explanation of the background to the caves in Zelda, and to /u/CroceaMors and /u/DoorToSummer for checking whether Tolkien thought there's a waterfall in Beowulf.