The first paper that comes to mind is this:
Clustering Via Decision Tree Construction
As another mentioned, "hierarchical" (top down) and "hierarchical agglomeration" (bottom up) are both well known techniques devised using trees to do clustering. Scipy has this.
If you are ok with custom code because I don't know of any library, there are two techniques I can recommend. Be warned that these are not technically clustering because of the mechanics they rely on. You might call this pseudo clustering.
1) Supervised: This is somewhat similar to the paper (worth reading). Build a single decision tree model to learn some target (you decide what makes sense). The target could be a randomly generated column (requires repeating and evaluating what iteration was best, see below). Define each full path of the tree as a "cluster" since points that fall through that series of branches are technically similar in regards to the target. This only works well on some problems, but it's efficient at large scale. You end up with K clusters (see below).
2) Semisupervised (sort of unsupervised, but mechanically supervised), using #1: you can try building trees to predict columns in a leave one out pattern. i.e. if the schema is [A,B,C], build 3 models [A,B] -> C, [A,C] -> B, [B,C]->A. You get KN clusters (see below). N=len(schema). If some of these features are not interesting or too imbalanced (in the case of categories), don't use them as targets.
Summary: The model will select features in order based on information or purity and clusters will be based on just a few features rather than all. There is no concept of distance in these clusters, but you could certainly devise one based on the centers.
Pros: easy to understand and explain, quick training and inference, works well with few strong features, works with categories. When your features are in essence heterogeneous and you have many features, you don't have to spend as much time deciding which to use in the distance function.
Cons: not standard, must be written, naive bias, collinearity with target causes bad results, having 1000 equally important features will not work well (KMeans with Euclidean distance is better here).
How many clusters do you get? You must, absolutely must restrict the DT model to not grow too much. e.g. Set min samples per leaf, max leaf nodes (preferred), or max depth. Optionally, set purity or entropy constraints. You must check how many clusters this gave you and evaluate if this method is better than real clustering.
Did the techniques and parameters work well for you? Which was best? To find out, you need to do cluster evaluation: Performance metrics to evaluate unsupervised learning