How do you do design change in TDD when you have such huge amounts of test that may be dependent on the existing implementation?
First, the best approach may be to avoid running into this situation at first hand, and refactor earlier. Often people forget that refactoring should be done rigorously in each TDD cycle, and design flaws should be removed as soon as they become apparent. Given there are so many tests as you said, I am pretty sure the design flaw was already apparent at a point in time when there existed a lot fewer tests.
But what can you do if you have already painted yourself into that corner? The problem here is usually the amount of test code which uses the public-facing API of the subject-under-test, which is what you want to change. So as an approach to resolve that problem,
Try to reduce the number of direct test calls to the public API by refactoring the tests themselves first and make them more DRY.
Build an anti-corruption layer (or facade, or proxy) between your tests and the SUT, so you can change the API of the SUT without having to change too many parts of your tests. That will allow you to keep the tests as they are for now. Later, when you have some time for cleaning up, you may decide to migrate the tests to the new API one-by-one.
The latter approach is also known as strangler pattern and used to gradually swap out legacy components by components with a new design.