Managed Package: How to get rid of dependency from Territory Management feature

As it's been stated before, you need to engage Partner Support. Once a managed package has a dependency on a feature, and a version with that dependency is uploaded, it cannot be removed by the ISV. This restriction is in place to allow for upgrades.

Finally we've figured it out.

All our code base in repository has already been cleaned up from territory dependencies. But at the same time there was some garbage left right on packaging org itself (some obsolete test classes etc.) probably someone forgot to add sf artifacts to destructive changes xml when removing them from repo.

After retrieving package from packaging org itself and comparing with snapshot in repository, we were able to identify and remove those obsolete artifacts. And this was enough, i.e. on next package upload TM feature was not ticked anymore as an auto-detected dependency.

So there is no need to involve SF support here. After cleaning up all explicit Territory dependencies, package really let it go by itself, even despite having previously released major versions currently installed on many clients orgs.