Most likely, the image is that of a barrel filled with fish and ice, which was how they were shipped. No way you could miss if you shot into that.
But there are many phrases that have no clear origin. Try looking up “rule of thumb” or “the whole nine yards.” Hell, no one is exactly sure the etymology of the word “bird.”* The majority of phrases and words have a clear etymology, but there are a large number of them that are no more than speculation.
*The anglo-saxon word is “fowle” and there was “brid,” meaning “brood,” but no one knows how that changed to “bird” – of if it actually did.