Best way to merge different trees to single data structure?
I don't think post-processing the trees to try to exploit similarity is likely to lead to much success.  Instead, I would suggest trying the following approaches, which to my mind seem more likely to be effective.

Tune the hyperparameters. Try adjusting the number of trees (num_iterations).  If you can get close to the same accuracy with fewer trees, the classifier will be faster.

Try a different classifier. There are other classifiers that are faster for evaluating new samples, especially in the multi-class regime.  For instance, you could try logistic regression and random forests.

Hierarchical multi-class classification. XGBoost is fundamentally a boolean classifier (where there are only two classes).  It handles  multi-class classification (with more than two classes) using the strategy one-vs-rest (or one-vs-all) strategy: if there are $K$ classes, then we construct $K$ boolean classifiers, where the $i$th either outputs "class $i$" or "not class $i$".  This is what leads to the blowup in number of trees: the running time is proportional to $K$.

If your classes have any hierarchical structure, then an alternative is to use a hierarchical structure.  You build a binary tree, where each leaf corresponds to a single class and each internal node corresponds to a set of classes (hopefully, ones that are semantically related).  You construct a classifier for each internal node of the tree, which predicts whether to go left or right down the tree.  You classify each new instance by walking down the tree, as directed by the classifiers that you visit.  Thus, with $K$ classes, we end up with a binary tree with $K$ leaves and of depth (typically) about $\lg K$.  Thus, you can classify a new instance by evaluating $\lg K$ classifiers.  This offers a speedup over one-vs-rest, because the time to classify a new instance is proportional to $\lg K$ rather than $K$.

However, hierarchical classification has some caveats.  It can potentially lead to reduced accuracy.  The effect on accuracy depends on the structure of the class labels.  If there is some hierarchical structure, then it might work well, but if not, it might work poorly.  For instance, suppose you have classes "Poodle", "Chihuaha", "Siamese", and "American Shorthair", you might group the first two into the cluster "Dog" and the latter two into the cluster "Cat".  Thus, you would first apply a Dog vs Cat classifier; then, depending on the result, you would either apply a Poodle vs Chihuaha classifier or a Siamese vs American Shorthair classifier.  So, hierarchical classification might work quite well in this example.  However, if your four classes are unrelated, hierarchical classification might cause a loss in accuracy.

Try a cascaded classifier.  Rather than building a single classifier, try to build a cascade of classifiers.  A cascade is a sequence of multiple fast classifiers, which are applied sequentially.  A classifier can either output a confident answer or can output "not sure"; in the former case, we stop and use that as the answer, and in the latter case, we proceed to the next classifier in the cascade.  The goal is that many instances will get answered quickly (you only have to apply the first few classifiers), and only the difficult ones will have to be evaluated by classifier in the sequence.