"Bull" meaning "nonsense" is derived from Old French boel, meaning fraud or deceit. Many lexicographers have debated as to when the four-letter Anglo-Saxon faecal reference was appended, one theory credits Australian and New Zealand troops in the First World War ridiculing their British allies with the term.
But living in an environment surrounded by hills full of cattle - and having more than once accidentally stepped in a fresh cow pat (while distracted by the beautiful views) - I can say that bullshit is a particularly unwelcome, sticky and smelly substance - which makes it a perfect metaphor for a lie.