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 auctioneer passed the cheap glasses into the audience, looking after them fondly and retaining the leatherette case in his hand. "You are now looking at what is without doubt the finest, most beautiful piece of workmanship you have ever held in your hand. Genuine Lemier! You all know what that means! Why, gentlemen and ladies, it's the same as the word 'sterling' stamped on silver, or '18 caret' on gold. It's money in your pocket if you buy this. It's an investment. Every gentleman must have have one. I'm bid dollar only"—he took a bid from one of his "shills" (another name for bid-boosters) in the audience.
...
A derisive laugh went up from the well-trained shills [at the auction] and Dougherty condescended to smile, for deep down in every man is a fondness for the stable article, for the fine thing that will last a lifetime, not for the showy fashion to be discarded to-morrow.
The shill beside Dougherty handed the watch back to to him at that psychological moment. ...
"You'd start it [the bidding] for a trifle—five dollars, surely?" prodded the auctioneer in a manner so evident that the shills themselves would have blushed at the imposition, were they not as case-hardened to that kind of crime as the auctioneer himself.
...
Dougherty glanced at the shill opposing his real money with mind money. Let that tall, pasty-faced gink beat him, get that little gem of a jewel of a watch that belonged to Mame—never!
The earliest Google Books match for shillaber, meanwhile is from Word-Lore: The 'Folk' Magazine, volume 1 (1926) [combined snippets]:
In this case an old circus trouper is the speaker, and his remarks are taken seriously, and a circus "glossary" is provided. (This glossary, by the way, includes the following curious item:—
Shillaber—An employee of the circus who rushes up to the kid show ticket box at the psychological moment when the barker concludes his spiel. He and his fellow shillabers purchase tickets and pass inside and the crowd of towners in front of the bally stand are not slow in doing likewise.
With which lucid explanation of course we know all about the shillaber. But the glossary is silent as to barker and spiel).
Earlier than that instance is one from "Grafters Go Glimmering," in the Tonopah (Nevada) Daily Bonanza (May 29, 1920):
Tonopah will have a sane and sensible Fourth of July without the raucous barking of the shillaber of the street carnival. The people of Tonopah expressed themselves in no unqualified tone when they learned what was contemplated for the national holiday week and forthwith sent up such a protest that the American Legion refused to be a party to shielding the fakers and dropped all negotiations. Merchants on Main street refused to sign a petition for use of that thoroughfare and the citizens of Brougher avenue turned a deaf ear to all appeals from the circus crew for consideration.
And from a full-page ad for "Big Auction Lot Sale," in the [Ardmore, Oklahoma] Daily Ardmoreite (May 16, 1920):
GUARANTEE[:] A certified check for $5,000 has been put in the hands of the Mayor of Grandfield as a forfeit to be paid to anyone who will prove that that there are any by-bidders, cappers or shillabers on the grounds. Absolute aution sale and everything above-board.
And earlier still, from W.W. Chapin, "Success: San Francisco's Symbol," in the San Francisco [California] Call (January 1, 1913):
It is the popular thing these days for the smaller cities to adopt what they call a "slogan," slogan being the battle cry of a barbarian, the shibboleth, as it were, of a shillaber. "Watch Bugleville Grow" they cry. "See Squashville Swell," or "Bungtown Booms." Amusing as such war cries are still their uses are like those of the bass drum of the Salvation Army.
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:
Another word with stress allegedly falling on the first syllable is shillaber (American slang), of which the OED, The Second Supplement, has only one 1913 example. The lexicographers on the present staff of the dictionary could not have heard it, for it has been dead for almost a century, and only its doublet shill 'decoy or accomplice, especially one posing as an enthusiastic or successful customer to encourage other buyers, gamblers, etc.' is in use. Shill is probably an abbreviation of shillaber (so in the OED), whose origin is said to be unknown. The development from shillaber to shill does not prove that the longer word had initial stress: cf. prof from professor and, conversely, 'burbs from suburbs. Could shillaber be an extended form of Germ. Schieber 'black marketeeer' (*shi-la-ber)?
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):
"The next big fight for the benefit of the Shillabers will be between Jack Johnson and Sam Langford. Don't overlook this. This match isn't so far away as you may think. I have it straight that Mistah Johnsing isn't doing so well in the theatrical line and I also know hat his financial state isn't any too healthy. ...
And from "Claims Men Are Fakers," in the Los Angeles [California] Herald (February 15, 1908):
Despite the warnings and repeated arrests by the prosecuting attorney, Edward J. Fleming, the barking peddlers of phony jewelry and jejeune junk, with other alleged peace disturbers, including cane-and-ring and similar rack gamblers, continue to ply their graft at Fifth and Main streets, in front of the Beaumont cafe, and also at Fifth and Los Angeles streets.
...
Frank Perkins, it is alleged, conducted a game in which the players tossed rings at silver money. Simpson and Dwyer are alleged to have been his assistants, known as "shillabers."
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):
The noble art of bunco—like tickling a man and picking his pocket—as practiced at Riverview is told by Jacob Le Bosky, attorney for some concessionaries of the park, in an action to investigate a receiver's report.
...
"The paddle wheels where candy and various other prizes were distributed with ever-r-y turn of the wheel were money makers. Some of them had 'shillabers' or 'shills,' employed by the owner of the concession.
"The 'shill' would buy a paddle and stand in the crowd with the rest. The man operating the wheel knew what numbers the 'shill' had on his paddle, so that when the wheel was turning, by means of a squeeze attached to the machinery, could stop it on a number which gave the prize to the 'shill.'
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.
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
According to the The New Partridge Dictionary of Slang and Unconventional English bung meaning to bribe is a UK slang expression from the '50s.
Bung
(Money Slang)
According to the following source "to bung" meaning to bribe is marked as "criminal slang" in the OED, and it usage may be traced back to the first part of the 19th century as a slang way of saying "to throw something with a little extra force."
(Kick the Bucket and Swing the Cat: The Complete Balderdash & Piffle ... by Alex Games)