an early occurrence is from Olympic Games by Isaac Cruikshank:
- In settle (someone’s) hash, to subdue, silence, defeat; kill: s. >,
in C.20, coll. An early occurrence is
in Isaac Cruikshank, Olympic Games, 16
June 1803 (thanks to Mrs M.D.George).
it's also in Americanisms: The English of the New World (1872) by M. (Maximilian) Schele de Vere - here's an image:

from hash:
1657, "to hack, chop," from Fr.
hacher, from O.Fr. hache "axe." The
noun "stew" is first recorded 1662,
from the verb.
My educated guess is that it's related to the the origins of the phrase "bury the hatchet", relevant quotes being:
"Bury the hatchet" is an Indianism (a
phrase borrowed from Native American
speech). The term comes from an
Iroquois ceremony in which war axes or
other weapons were literally buried in
the ground as a symbol of newly made
peace. The other two languages spoken
by Europeans in close contact with the
Iroquois in and around what is now New
York state also use the phrase:
enterrer la hache de guerre and de
strijdbijl begraven. (I leave it as an
exercise for the reader to determine
which is French and which is Dutch.)
and
The first mention of the practice in
English is to an actual
hatchet-burying ceremony. Years before
he gained notoriety for presiding over
the Salem witch trials, Samuel Sewall
wrote in 1680, "I writt to you in one
[letter] of the Mischief the Mohawks
did; which occasioned Major Pynchon's
goeing to Albany, where meeting with
the Sachem the[y] came to an agreemt
and buried two Axes in the Ground; one
for English another for themselves;
which ceremony to them is more
significant & binding than all
Articles of Peace[,] the hatchet being
a principal weapon with them."
So between MikeVaughan's answer that it's related to the French word for "axe" & the practice of "burying the hatchets", I'm inferring that "settle someone's hash" came from these ideas.