From the Online Etymology Dictionary:

"eloquent and insincere rhetoric," 1915, American English slang

The suggestion is that the slang term is a combination of the swearword shit with the word bull, both in reference to the animal, but also to an older meaning dating from the 15th century:

bull (n.3) "false talk, fraud," Middle English, apparently from Old French bole "deception, trick, scheming, intrigue," and perhaps connected to modern Icelandic bull "nonsense."

Sais christ to ypocrites ... yee ar ... all ful with wickednes, tresun and bull. ["Cursor Mundi," early 14c.]

There also was a verb bull meaning "to mock, cheat," which dates from 1530s.

If that's the case, it could be that it was made up as a handy combination of a swearword + a pre-existing term that also worked as a handy animal pun(which we all know people love!)

The Oxford Dictionary has the same definition of bull dating to the 17th century, origin unknown. The OED also gives the same origins for bullshit - that meaning combined with the word shit.

Also, note that one of the standard definitions of shit is as an adjective referring to something as 'nonsense' or 'worthless' - that would make it a good combination word with bull for the purposes we're looking at, as opposed to calling something a bullfuck(or a fuckbull?). The swear word was taboo, but it also had a meaning that was analogous to the word it was being attached to.