I watched this film like 5 times when I was 10 and I've been struggling for two years now to find it. I remember it being rather bloody and gory, and the animation style I believe can be described as explicit, somehow realistic.
I think it was a story about native-Americans, a tribal vibe nonetheless. I remember the opening scene, a river, grass, next to a forest. I remember cannibalism scenes, some neanderthal-like creatures with black eyes that creeped me out, flesh of dead animals hanging from trees and lots of blood. I think the main character was fighting the aforementioned humanoids. The whole thing had a fantasy, demonish feel to it (for a 10 year old, I guess).
I also think it was created after 1990 and before 2004.