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 could have been spotted much earlier, 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 a facade, or a 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 can often be used to gradually swap out legacy components by components with a new design, not only for tests.
As an example, if you have 50 tests calling the same public method of a class (and maybe only one or two places in your production code calling the same method), then the tests seem to hinder you changing the signature of that method. But if most of the direct calls inside the test code are rerouted through a single helper method, maybe one which also does parts of the arrange-act-assert work, it will become a lot simpler to change the method signature of the SUT.