I started the search by looking at the simple quote ["Elementary, my dear Watson"] with no restrictions. Lots of pages state that the first recorded use of the prhase is P. G. Wodehouses novel Psmith, Journalist.
However, I found an earlier use of the phrase: In 1912 it was used in the publication The Sketch: A Journal of Art and Actuality, Volume 77 with The Ingram Brothers as authors. I found the result by using the query ["Elementary, my dear Watson"] with the time restriction set for anything earlier than 1915. It is also possible to find another result from 1912. It has the same title but lists F. Barnard as author.