Multiple categories within a variable in decision tree
Your intuition that a categorical feature is treated as multiple dimensions (i.e., multiple features) is correct. Millions of categories will be problematic for tree-baed algorithms that search through all features/categories for each split. A random forest would be a good model to try for your project, since it samples the features. Most software implementations let you set the sample proportion, so you could set yours really low if need be to speed up the split searches. 

Alternatively you could feed your dataset into a Lasso or Elastic Net model to remove noisy variables and substantially reduce the quantity of categories under consideration. Lasso and Elastic Net have both been shown to do well on datasets where the number of features far exceeds the number of observations (e.g., dealing with genome data).