"weary by too much, fill to loathing, surfeit," 1520s, from Middle English cloyen "hinder movement, encumber" (late 14c.), a shortening of accloyen (early 14c.), from Old French encloer "to fasten with a nail, grip, grasp," figuratively "to hinder, check, stop, curb," from Late Latin inclavare "drive a nail into a horse's foot when shoeing," from Latin clavus "a nail" (from PIE root *klau- "hook").
Accloye is a hurt that cometh of shooing, when a Smith driveth a nail in the quick, which make him to halt. [Edward Topsell, "The History of Four-footed Beasts," 1607]
The figurative meaning "fill to a satiety, overfill" is attested for accloy from late 14c. Related: Cloyed; cloying.