Where did the phrase "Iä! Iä! Cthulhu fhtagn!" first appear?

Question

There is a phrase that is pretty commonly known to fans of H.P. Lovecraft's Cthulhu mythos (whether or not they've actually read the stories or not):

Iä! Iä! Cthulhu fhtagn!

Sometimes a longer version of the phrase comes up as well (untranslated in his stories*):

Iä! Iä! Cthulhu fhtagn! Ph'nglui mglw’nafh Cthulhu R'lyeh wgah'nagl fhtagn!

This phrase reappears in a lot of derivative Cthulhu works. For instance, the board game Arkham Horror has the text on the Cultist monster. There is even an Urban Dictionary definition that mentions this exact quote. And of course, there are memes:

I figured that this phrase came from The Call of Cthulhu, but a quick search of the text shows that the phrase doesn't appear exactly that way:

He talked of his dreams in a strangely poetic fashion; making me see with terrible vividness the damp Cyclopean city of slimy green stone—whose geometry, he oddly said, was all wrong—and hear with frightened expectancy the ceaseless, half-mental calling from underground: “Cthulhu fhtagn”, “Cthulhu fhtagn”.

Note that while close, the words "Iä! Iä!" are not used here or anywhere else in the story.

The second part of the phrase does appear in the story, but isolated from "Cthulhu fhtagn"

What, in substance, both the Esquimau wizards and the Louisiana swamp-priests had chanted to their kindred idols was something very like this—the word-divisions being guessed at from traditional breaks in the phrase as chanted aloud:

“Ph’nglui mglw’nafh Cthulhu R’lyeh wgah’nagl fhtagn.”

So where does the phrase "Iä! Iä! Cthulhu fthagn!", and the longer version of the phrase, first appear?

Note, I'm looking for the exact phrase, not variations of the phrase or the phrase in fragments, although knowing about the evolution of the phrase would certainly be interesting supporting material.

^{* This phrase is in a language that Lovecraft made up. It's not translated in the stories, but the internet seems to translate it as "Hail! Hail! Cthulhu dreams! In his house at R'lyeh, dead Cthulhu waits dreaming!" I'm not sure where this translation originated.}

Answer 1

It comes from his story "The Shadow Over Innsmouth", where a character named Zadok says:

"Yield up enough sacrifices an' savage knick-knacks an' harbourage in the taown when they wanted it, an' they'd let well enough alone. Wudn't bother no strangers as might bear tales aoutside—that is, withaout they got pryin'. All in the band of the faithful—Order o' Dagon—an' the children shud never die, but go back to the Mother Hydra an' Father Dagon what we all come from onct—Iä! Iä! Cthulhu fhtagn! Ph'nglui mglw'nafh Cthulhu R'lyeh wgah-nagl fhtagn—"

(using the spelling and punctuation from this edition)

Wikipedia mentions here that this story was written in November-December 1931, while a search on google books shows that Lovecraft had earlier (not sure if this was the first time) added "Iä" to a sentence containing "Cthulhu fhtagn" in a letter written on Oct. 31 1930, quoted in Selected Letters, Volume III on p. 200.

"Cthulhu fhtagn! Cthulhu fhtagn! Iä! Shub-Niggurath! The Goat with a Thousand Young!"

But note that here it appeared after "Cthulhu fhtagn" rather than before, and as A Simmons points out in a comment, it's quite possible Lovecraft intended it to be paired with the phrase "Shub-Niggurath" that follows it, since Lovecraft had previously used the phrase "Iä! Shub-Niggurath!" in his story "The Dunwich Horror" from 1928.

Answer 2

To cover the footnote of the question, the translation also appears in The Call of Cthulu:

Legrasse had one point in advance of Professor Webb, for several among his mongrel prisoners had repeated to him what older celebrants had told them the words meant. This text, as given, ran something like this: "In his house at R'lyeh dead Cthulhu waits dreaming."