The current implementation is fast enough for short message, but becomes very slow for anything over 10 kB. It seems that the asymptotic performance is worse than O(n).
Now I've realized that the O(n) performance is (likely) not possible. Base62 encoding is essentially radix conversion from base 256 to base 62 and based on quick search, the best known bound is O(M(n) log n) where M is the bound for multiplication of two n-bit integers. Still, it would be good to do a small benchmark to check the performance against the other implementations.
(Base64 is a special case since 256 is a multiple of 64.)