Is this simply because if we have a lot of data, there is a bigger chance that a more complicated decision boundary (boundaries) is required to separate the observations? Does someone know researches who published papers about the performance of these techniques depending on the data size?
Thinking of "decision boundaries" and dichotomization in general is not the best way to think about data. And trees do not usually perform better than regression on large datasets, because trees (e.g., recursive partitioning; CART) do not handle continuous variables well and because they give equal belief to high-order interactions as to main effects. Trees require much larger datasets than regression (typically 200 events per candidate variable whereas logistic regression requires 20 events per candidate variable) in order to be reliable. So trees are disasters on small datasets, and are nothing to be excited about for large ones.
This is the related to the reason people use combinations of trees such as random forests. Individual trees just don't work well. But combining trees loses the only advantage (interpretability) that trees ever offered.