Transitive meaning "move (something) back and forth or up and down" is from c. 1300; of dogs and their tails from mid-15c.: "and whanne they [hounds] see the hure maystre they wol make him cheere and wagge hur tayles upon him." [Edward, Duke of York, "The Master of Game," 1456]. Related: Wagged; wagging. Wag-at-the-wall (1825) was an old name for a hanging clock with pendulum and weights exposed.
c. 1500, kind of small bird that has its tail in continuous motion (late 12c. as a surname), earlier wagstart (mid-15c.), from wag (v.) + tail (n.). From 18c. as "a harlot," but this sense seems to be implied much earlier:
If therefore thou make not thy mistress a goldfinch, thou mayst chance to find her a wagtaile. [Lyly, "Midas," 1592]
"servile or insincere praise," late 14c., from Old French adulacion, from Latin adulationem (nominative adulatio) "a fawning; flattery, cringing courtesy," noun of action from past-participle stem of adulari "to flatter, fawn upon."
This is usually said to be from ad "to" (see ad-) + a stem meaning "tail," from a PIE *ul- "the tail" (source also of Sanskrit valah "tail-hair," and Lithuanian valai "horse's tail"). The original notion would be "to wag the tail" like a fawning dog (compare Greek sainein "to wag the tail," also "to flatter;" also see wheedle).
But de Vaan finds phonetic problems with these and concludes the etymology is uncertain, though he proposes a connection with avidus "eager," via *adulo- "who is eager toward something," hence "a flatterer." Adulation may proceed from true blind worship or be insincere, from hope of advantage.