Some time later the tax man comes by. He asks to see my tally sticks from last year. Oops, now I have a problem! I need records, databases, immutable data structures, extra book keeping work. Incidental complexity.
What am I missing in my shepherds tale?
Your analogy is quite good, but I don't think it unambiguously supports mutable data structures.
The abacus will let you count faster, but is a bad medium for long-term storage. A stick with notches isn't exactly immutable, since you can cross over notches, so in a sense they're mutable but only additively. If you glue the beads of the abacus it becomes better than a stick with notches for bookkeeping but worse for counting.
You can evaluate data structures outside of computers perfectly fine like this. I would even say that this isn't figurative speech or metaphor: We're actually analysing the time and space complexity of real-world data structures. Once we get to von Neumann-style computers, the materials (RAM, CPU, etc.) just have a different cost profile which make some analogical comparisons break down a little.
A very strong property of immutable data is that you can refer to it from other data and know that it won't eventually become invalid. So immutable data can be used to annotate other immutable data (or other mutable data, for that sake, but then this recursive property is instantly lost). This is the bookkeeping part.
The radical idea of using functional or otherwise declarative programming for general purposes (rather than very domain-specific ones) comes from the observation that often the cost of immutable data structures is well within acceptable limits of our materials. And because computer programs often do a mixture between counting and bookkeeping, you get the benefits of persistency at more levels.
When the cost of immutability is too high, Haskell has come up with the
ST monad, which is a type-safe way to mutate a value locally. When the cost of mutability is too high, Rust has come up with borrowed types. These notions may essentially express the same machine-level operations.
Whether you decide to complicate your program with "pure data" or "linear types", the justification is in both cases that more constraints will provide for more efficient compilation and execution strategies, at the cost of mental overhead to the programmer. So if you think e.g. linear types are worth pursuing, you're probably closer in mindset to a purely functional programmer than you think, sans the extremist attitude.