As with many phrases with which almost everyone is familar, the actual genesis is difficlut to determine. A veritable florilegium of attributions is available and seems to center on novelist Mary Roberts Rinehart (1876-1958), who wrote dozens of popular books, starting with The Circular Staircase in 1908. In 1930 she published The Door, in which the butler actually does it. However, the problem arises in that she never employed the phrase.
The Oxford Companion to Crime & Mystery Writing adds a sampling from Arthur Conan Doyle's The Musgrave Ritual where we find "...the butler, guilty of betrayal and theft, paid with his life for his perfidy", but, alas, no actual phrase.
Finally, in an essay entitled Twenty Rules for Writing Detective Stories, the author, S.S. Van Dine includes this tid-bit: "A servant must not be chosen by the author as the culprit. This is begging a noble question. It is a too easy solution. The culprit must be a decidedly worth-while person--one that wouldn't ordinarily come under suspicion", seeming to inveigh against the stock phrase.
So, all in all, not much deffinitive helps, I'm afraid...