Back on Scott Aaronson's blog, I gave an argument that $e^z+z-1$ should have an analytic compositional square root. The important difference between this function and $e^z-1$ was that the fixed point at $0$ has derivative $>1$, not $=1$. This should warn us that arguments based on the growth rate near infinity are inadequate. (Or else it should point out that my argument was broken!)

See comments below, my argument may have been broken. But, if so, I want to figure out why!

UPDATE: OK, I'm looking for some empirical data myself now. Let $e(z)=e^z+z-1$. My argument claimed that there should be an analytic and invertible $u$ (near 0) such that $u(e(z)) = 2 u(z)$. If such a $u$ exists, then $u^{-1}(2^{1/2} u(z))$ should have the desired property.

The nice thing about the equation $u(e(z)) = 2 u(z)$ is that it is linear in the coefficients of $u$. Here are the first 10 coefficients, computed with exact arithmetic.

{1, -(1/4), 1/18, -(1/96), 17/10800, -(47/267840), 4069/354352320,
-(24907/102863416320), 475411/2893033584000, -(108314387/
1314080143488000)}

And the numerical versions of the above

{1., -0.25, 0.0555556, -0.0104167, 0.00157407, -0.000175478,
0.0000114829, -2.42137*10^-7, 1.6433*10^-7, -8.2426*10^-8}

They seem to be converging rapidly.

Going a little further up, something odd happens. I computed the first 20 terms, of $u$, still using exact arithmetic, and I computed the ratios of successive terms. I'll just give you numeric data, because the fractions are huge.

{-0.25, -0.222222, -0.1875, -0.151111, -0.11148, -0.065438,
-0.0210867, -0.678665, -0.50159, -0.155914, 0.12897, -0.691029,
-0.153086, 0.158892, -0.657229, -0.165837, 0.119535, -0.806045,
-0.191576}

So the ratios are usually small, but occasionally they jump up to larger than 0.5. That's still not evidence against convergence, but it suggests a need for caution (or the possibility of a bug!)

On the other hand, I also tried computing the $k$-th roots of successive terms, and the behavior was much smoother:

{1., 0.5, 0.381571, 0.319472, 0.275046, 0.236612, 0.196922, 0.148939,
0.176275, 0.195707, 0.191704, 0.185475, 0.205223, 0.200971, 0.197848,
0.213264, 0.210132, 0.203648, 0.218941, 0.217484}

Again, this is exact up until the point of taking a $k$-th root of a rational number.

UPDATE: Ok, I went and tried to repeat Ekhad's computation, and I think that Michael Lugo has found the error. Let $f(f(z)) = e^z+z-1$. I just did the first 5 terms, and I get:

Coefficients of $f$: {Sqrt[2], 1/4 (2 - Sqrt[2]), 1/36 (-9 + 7 Sqrt[2]),
1/288 (47 - 33 Sqrt[2]), (-4350 + 3071 Sqrt[2])/43200}

Table of $|f_i|^{1/i}$: {1.41421, 0.382683, 0.292347, 0.184117, 0.174302}

Table of $(i! |f_i|)^{1/i}$: {1.41421, 0.541196, 0.53123, 0.407517, 0.454086}

Notice that my second table, not my first, matches Ekhad. But my first table is the right thing to compute.

3more comments