J.S. Farmer & W.E. Henley, Slang and Its Analogues (1904) has the following entry for tootsie:
Tootsie, subs. (common).—A foot : spec. of women and children.
1897 MARSHALL, Pomes, 46. Towards her two TOOTSIES ... she gazed with a feeling of fear ... But her hose were well veiled from man's sight.
John Hotten, The Slang Dictionary: Or, the Vulgar Words, Street Phrases, and "Fast" Expressions of High and Low Society (1869) has this amusing entry:
TOOTSIES, feet, those of ladies and children in particular. In married life it is said the husband uses this expression for the first six months, after that he terms them HOOFS.
A Google Books search finds a first match for tootsies from Jane Weaver, "The First Baby," in The Peterson Magazine (February 1852):
"Did you ever see such a darling?" she [the mother] cried, tossing the infant up and down in her arms. "There, baby, that's ma's old friend, Jane. She knows you already, I declare," cried the delighted parent, as it smiled at a bright ring, which I held up to it. "You never saw such a quick child. She follows me with her eyes all about the room. Notice what pretty little feet she has: the darling footsy-tootsies,” and taking both feet in one hand, the mother fondly kissed them.
"Footsy-tootsies" makes another appearance in Charles Leland, Meister Karl's Sketch-book (1855):
Yes, this is fine weather for the juveniles ; and mightily do they enjoy it. The more aristocratic are now elaborately equipt in short-tailed frocks, with plaid gaiters on their little footsy-tootsies; and with a yard of broad ribbon behind, and a mighty hat with a trailing feather on their heads, are led forth, looking like hand-organ monkeys out for a walk, ...
The earliest instance I could find of tootsies being used to refer to the feet of a woman, rather than a baby or young child is in this memorable couplet from "The Periwinkle Girl" in Chambers's Journal (August 21, 1869)"
Both high and low, and great and small, fell prostrated at her tootsies ;
They all were noblemen, and all had balances at Coutts's.
The earliest instance in a Google Books search of Tootsie as a pet name for a girl or young woman is from R. Mounteney Jephson, The Girl He left Behind Him: A Novel (1876):
"Yes, I saw the daughter when I called," said Garstang. By Jove! sir, she fetched me uncommon! a devilish taking little thing, eh ? Why do they call her 'Clive,' though? Queer name for a she-male. Should have thought 'Flossie' or 'Tootsie' or something in that style would have been more in her line."
And the earliest instance where Tootsie appears as a lovey-dovey name for a sweetheart is from "A Guilt Chain," in Truth (December 25, 1880), based (it appears) on "Pat-a-Cake, Pat-a-Cake":
Happy thought! happy thought! Goldsmith's man,
Make me gold fetters as soon as you can!
Mould them, and beat them, and mark them A B,
And have them in order for Tootsie and me!
The form Toots appears as a girl's familiar name in S. Alice Callahan, Wynema: A Child of the Forest (1891):
It would seem as yesterday if Robin were not such a tall, broad-shouldered fellow, really towering over us all; and I, a cross-grained, wrinkled spinster; and Toots putting on young lady's airs—I suppose we shall have to call her Bessie, now; and even Winnie, our dear, little baby, is laying aside her dolls and—I really do believe it, Miss—is smiling at Charley or Willie or Ted.
So it appears that the expression from which toots eventually arose began as the (parental) baby-talk compound footsy-tootsie (meaning an infant's or child's foot), which subsequently appeared in the alternative forms tootsie-pootsie and tootsie-wootsy and in the shortened form tootsie; and from there the word expanded to apply to women's feet. By 1876 Tootsie was in use as a pet name for girls or women, and by 1891 Toots was.
UPDATE (January 12, 2017)
An Elephind newspaper database search turns up an early instance where "tootsie" appears as part of a baby talk description of an infant (and not specifically of the infant's toes). From "A Baby and a Merry Editor," in the [Oregon, Missouri] Holt County Sentinel (February 8, 1867):
"...And it [the baby] is ours to keep. We can watch it as it grows, and be glad when it learns to laugh, and sit on the floor, and to tumble over on its back, and put its big toe in its mouth, and to stand alone, and to walk, and to climb up on the table, and to cut holes with the scissors in its mother's dresses." "De sete 'ittle pootsey tootsie!"
Likewise, "A Proper Thing to Do," in the Tiffin [Ohio] Tribune (July 5, 1877), reprinted from the Washington [D.C.] Star, has this:
At a meeting of the Board of Public School Trustees last evening Trustee W. H. Browne, in presenting the list of teachers of the second district for confirmation, noticing that a large proportion of the first names terminated with the fashionable and foolish "ie," called attention to the fact and changed them to the proper names in each case, except that of Miss Dalton, who was christened Sallie. This was a proper thing to do. The Mamie, Nellie, Bellie, Mattie, Nannie, Sallie, Fannie, Jennie, Minnie, Virgie, Lollie, Mellie line of pet names may do for the ittie, tootsie, pootsie, pupils of an infant school, but when young ladies have reached years of discretion, entitling them to take the responsible position of teachers in our public schools, they should drop these tender nursery diminutives; and if they do not do it of their own volition the school Board should do it for them.
A person writing a letter to the editor of the New York Sun (January 20, 1871) signs herself "Madame Tootsie"—seemingly a pseudonym, but the name choice is unexplained, so its historical value is rather dubious.
A very brief glossary titled "Matrimonial Dctionary," originally printed in Punch but reprinted in the Bell's Life in Sydney [New South Wales] and Sporting Reviewer (March 27, 1847) has this:
Tootsy, Mootsy, and all words ending in tsy, are terms of great endearment. The exact meaning of them has never been ascertained. They are never heard after thirty.
...
Toodledums.—See Tootsy.
The term "footsy-tootsy's" shows up in the same newspaper less than six months later, on September 4, 1847:
A correspondent says, that he occupied a chamber separated from that of a married couple by a thin partition. One cold night he hard the rough voice of the husband grumble out—"Take away your hoofs!" to which the wife replied, in a querulous tone—"Ah! you did not speak so to me when we were first married—then you used to say to me, 'Take away your little hootsy footsy tootsy's!'"
This may in fact be the source of the jest passed along by Hotten in his Slang Dictionary 22 years later. Many other newspapers related the same anecdote over the course of the next decade.
In any event, it appears that tootsy/tootsie/toots has been around a very long time as a sort of infantalized expression of affection.
Best Answer
A Google Books search finds multiple instances of shill in the sense of "accomplice" from Robert Brown, "The Watch," a short story set in an auction in New York City, in The Metropolitan Magazine (April 1911):
The earliest Google Books match for shillaber, meanwhile is from Word-Lore: The 'Folk' Magazine, volume 1 (1926) [combined snippets]:
Earlier than that instance is one from "Grafters Go Glimmering," in the Tonopah (Nevada) Daily Bonanza (May 29, 1920):
And from a full-page ad for "Big Auction Lot Sale," in the [Ardmore, Oklahoma] Daily Ardmoreite (May 16, 1920):
And earlier still, from W.W. Chapin, "Success: San Francisco's Symbol," in the San Francisco [California] Call (January 1, 1913):
Anatoly Libermn, "Extended Forms (Streckformen) in English," in Studies in the History of the English Language II: Unfolding Conversations, cites The Oxford English Dictionary as having an example of shillaber from 1913:
But unless the OED's instance from 1913 is the item from the January 1, 1913, San Francisco Call, the latter probably antedates the OED's example. In addition to this item, the Chronicling America newspaper database finds two matches from before 1913. From "Blacks May Get Together Next," in the [Grand Forks, North Dakota] Evening Times (September 12, 1910):
And from "Claims Men Are Fakers," in the Los Angeles [California] Herald (February 15, 1908):
Also of interest is an item from 1915 that explicitly connects shillabers and shills. From "Says Summer Park Games Couldn't Be Beaten," in the Chicago [Illinois] Day Book (October 29, 1915):
Conclusions
The term shill in the sense of "accomplice" goes back at least to 1911; and the term shillaber in the same sense goes back at least to 1908. An article published in 1915, when both terms were in active use, explicitly describes them as alternative words used to describe the same thing.
Usage seems to have spread fairly rapidly across the United States. By 1915, instances of shillaber and/or shill had appeared in periodicals in Los Angeles (1908), New York (1911), San Francisco (1913) and Chicago (1915)—but also in Grand Forks, North Dakota (1910).
Unfortunately, none of the early matches for shillaber gives any hint of where the term came from and what earlier word or person (if any) the term is based on. A New England humorist named Benjamin Shillaber had invented a character named Mrs. Partington, who became famous for such remarks as that she never worried about the price of flour because whenever she bought 50 cents worth, it always cost the same—but Shillaber died in 1890, and he seems to have contributed nothing toward the bunco arts.
Leo Rosten, who isn't shy about asserting Yiddish influences on U.S. English speech patterns and vocabulary, makes no claim for an association between shill or shillaber and any Yiddish word. I think this is another case where "origin unknown" continues to be the safest call.