Some updates on this:

I opened a PR that's about to be merged and will reduce MAE criterion complexity from O(n^2) to O(n log n). MAE will still be quite slower than MSE: 3-6x times slower, but that's it.

A PR to add the support for pinball loss (~= quantile regression), should follow-up.

Also note that building a decision tree always has a complexity of O(n log n) as it requires sorting target vaules according to feature values (at each depth of the tree).