The 1929 film. The usual culprit named online is The Return of Sherlock Holmes, the first Sherlock Holmes sound film, which ends with the line. It is a popularizer, not a source: the phrase was in print by 1908, twenty-one years earlier.
P. G. Wodehouse. Psmith murmurs “Elementary, my dear Watson, elementary” in Psmith, Journalist — a genuine early appearance, and one you can read for yourself. But it is a joke told at the reader’s expense, and it only lands if the reader already knows the line. Wodehouse is quoting the street, not inventing the phrase.
William Gillette. Sherlockians have long suspected the actor whose 1899 stage Holmes defined the character for a generation. It is a real hypothesis and it is unproven. The text of the play has Holmes say to Watson only: “Elementary! The child’s play of deduction!” The theory is that years of performance, and audiences blending two familiar phrases, did the rest — which, if true, is not an origin so much as a description of the same collective process.