Bully already had a variety of usages by the late 18th century. The following from Francis Grose, Dictionary of Buckish Slang, University Wit and Pickpocket Eloquence:
Bully- from bullock- bully, to hector, bounce or bully.
Bully- a cowardly fellow, who gives himself airs of great bravery.
Bully Back- a bully to a bawdy house.
Bully Cock- One who foments quarrels in order to rob the persons quarrelling.
Bully Ruffians- Highwaymen who attack passengers with oaths.
Bully Trap- a brave man with a mild or effeminate appearance, by whom bullies are taken in.

Origin of Word- OED
The I. definition remains a term of endearment or familiarity ("Possibly" Dutch boel: lover, brother, buddy, etc.). Unlikely from Sc. billie, or brother). This meaning came into English use in the 16th century.
II. Hector, and all the meanings given by Grose, above. These appeared in print from 1688, but the quotations lead one to the conclusion that the meanings of ruffian and/or bawdy's protector are earlier.

Bully- a shepherd's cottage- from 16th century in print.
Bully beef- 19th century.

And don't forget Theodore Roosevelt, who popularized 'bully' as a term for great or wonderful back around 1900.