One possible origin of the idiom was that red herring were used to train dogs to track scents. This was true, but the modern meaning of a false trail may have been popularised in a news story by English journalist William Cobbett, c. 1805, in which he claimed that as a boy he used a red herring (a cured and salted herring) to mislead hounds following a trail; the story served as an extended metaphor for the London press, which had earned Cobbett's ire by publishing false news accounts regarding Napoleon. The OED has another possible earlier origin in the legacy of clergyman Jasper Mayne in 1672 when he misled a servant by leaving him "Somewhat that would make him Drink after his Death" in a large trunk. When the trunk was opened, the contents were found to be red herring.
1997, David Foster Wallace, “David Lynch keeps his head”, in A Supposedly Fun Thing I'll Never Do Again, Kindle edition, Little, Brown Book Group:
By its thirtieth episode, the show [Twin Peaks] had degenerated into tics and shticks and mannerisms and red herrings, and part of the explanation for this was that [David] Lynch was trying to divert our attention from the fact that he really had no idea how to wrap the central murder case up.
2012 March 1, Elizabeth Peters, Children of the Storm (Amelia Peabody), Hachette UK, →ISBN, →OCLC:
I will, of course, turn my analytical talents to bear on the identity of the imitation Hathor, but in my opinion she is only a red herring – a nuisance, a distraction.
Colombia is a red herring, however. The songs that became Madame X actually came together during Madonna’s two years in Portugal, where she decamped in 2017 when her son David enrolled in Benfica’s football academy.
“Devil a bit, Ma’am,” said the Major. “We couldn’t afford it. Unless the world was peopled with J.B.’s—tough and blunt old Joes, Ma’am, plain red herrings with hard roes, Sir—we couldn’t afford it. It wouldn’t do.”