There seems to be a lot of “reasoning” because you are unfolding the recursive calls in your mind.
A simpler way to look at it is to rephrase it like this:
The first function tells if a number n is even by using this rule: if n is 0, then n is indeed even. Otherwise, it is even if (n-1) is odd.
The second function tells if a number is odd by comparing it to 0: if it is 0, then it is not odd. Otherwise, it is odd if n-1 is even.
I think this is quite understandable, and also literally what the program is doing.
Then of course, you also have to convince yourself that these mutually recursive functions do terminate, and that is easy to check that they will for any n>=0.
Frankly, I doubt you could come by an example much simpler than this one.