Yeah, backtracking in parser combinators libraries is a mess in theory (and in my opinion hard to reason about in practice too). Another big problem is that the backtracking is done naively if it is done properly at all, so it can easily cause exponential blowup of running time.
It is possible to have O(n) running times (for unambiguous grammars) with proper backtracking, by using memoization. The biggest problem with that is that the library needs to know where the recursion is happening, but you can’t really see that from inside Haskell. I floated a bunch of ideas in another topic here: Reusing Haskell's binding when defining context free grammars.
I didn’t pursue those much further because I haven’t yet fully understood the state of the art algorithms, but I did manage to squeeze a paper out about formalizing the semantics in Agda: A Type Theoretic Treatment of Context-Free Languages Without Mutual Recursion. I would like to expand that line of work when I have time again.