This doesn't sound so much as too much coverage but rather like having your automated tests be coupled to implementation details. This has a multitude of possible causes, for example too the tests being too granular (prefer testing at the boundary of your system). I've worked in codebases where test-implementation detail coupling was taken seriously, and in those I've rarely had to write a commit message like "fix tests", and all that without losing coverage.
Changing specifications and code which turns out to be unnecessary aren’t ideal. but I believe they’re inevitable to some extent (unless the project is a narrow re-implementation of something that already exists). There are questions like “how will people use this product?” and “what will they like/dislike about it?” that are crucial to the specification yet can’t be answered or even predicted very well until there’s already a MVP. And you can’t know exactly what helper classes and functions you will use to implement something until you have the working implementation.
Of course, that doesn’t mean all tests are wasted effort; development will be slower if the developers have to spend more time debugging, due to not knowing where bugs originate from, due to not having tests. There’s a middle ground, where you have tests to catch probable and/or tricky bugs, and tests for code unlikely to be made redundant, but don’t spend too long on unnecessary tests for unnecessary code.
Then there's the second level of proficiency, related to what you're discussing with "test-implementation detail coupling". This is the domain of high test coverage, repeatable end-to-end tests, automated QA, etc. I've always struggled with this next level and I've yet to work in any environment where it was done effectively (if at all). It's also harder to argue for this kind of testing because the tests often end up brittle and false negatives drown out the benefits.
Moreover, most of the discourse centers around the first level of proficiency only and it's much harder to find digestible advice for achieving the second.
Depending on how high coverage you are aiming for, I find it hard to imagine a way to achieve it without inevitably tying the tests to implementation details
There will always be some coupling between test and testee (for example, if I change my `double` function from doing `x -> 2 * x` to `x -> (x, x)`, my tests for `double` better fail), but there is a lot of coupling which is unnecessary, and this can often be removed. Like decoupling any two pieces of code, there is no one size fits all solution. There are some common sources of unnecessary coupling, and some rules of thumb to avoid them.
For example, let's say we have a (public) sorting routine `sort` which consists of two (private) phases: `prep` and `finish`. The implementation of `sort` would look like
function sort(xs):
prepped_xs = prep(xs)
return finish(prepped_xs)
The first is quite simple, just chuck in a bunch of unsorted arrays of varying sizes and degrees of unsortedness, and assert that what comes out is sorted:
assert sort([]) == []
assert sort([3, 2, 1]) == [1, 2, 3]
etc
x = [1, 2]
sort(x)
mocked_prep.assert_called_with(x)
// and something similar for finish
assert is_prepped(prep([1, 2]))
etc
assert is_sorted(finish(prepped_xs))
etc
So here, by increasing the scope of your test suite from `prep` and `finish` to `sort`, you've achieved looser coupling between the test suite and what is being tested. This can be applied much more generally: by testing at the boundary of your system (at a higher scope), you achieve looser coupling between your tests and your code. That is, you'll have fewer false failures.
But you won't have very good coverage of "prep" or "finish"
You can of course test those functions by carefully constructing test cases for "sort", but that essentially just re-introduces the coupling to implementation details at a higher level