1530s, "sweetheart," a term of endearment applied to either sex, of uncertain origin; perhaps from Dutch boel "lover; brother," which probably is a diminutive of Middle Dutch broeder "brother" (compare Middle High German buole "brother," source of German Buhle "lover;" see brother (n.)).
Meaning deteriorated 17c. through "fine fellow" and "blusterer" to "harasser of the weak" (1680s, from bully-ruffian, 1650s). Perhaps this was by influence of bull (n.1), but a connecting sense between "lover" and "ruffian" might be "protector of a prostitute," which was one sense of bully (though it is not specifically attested until 1706). "Sweetheart" words often go bad in this way; compare leman, also ladybird, which in Farmer and Henley ("Slang and Its Analogues") is "1. A whore; and (2) a term of endearment." Shakespeare has bully-rook "jolly comrade."
The adjective meaning "worthy, jolly, admirable" is first attested 1680s, and preserves an earlier, positive sense of the word. It enjoyed a popularity in late 19c. American English, and was used from 1864 in expressions, such as bully for you! "bravo!"