Your argument for three exponentials can be simplified a bit by using the multiplicative version of van der Corput instead of the additive version. Specifically, if your equation $$2^{y^{2^k}} = 2^{y} + k \quad(\ast)$$ has many solutions then there is some bounded $l>1$ such that there are many pairs of solutions $y,ly$, and for any such pair we must have $z=2^y$ solving $$(z+k)^{l^{2^k}} = z^l + k,$$ which of course has a bounded number of solutions. (Equivalently, write the equation in terms of $y' = 2^x$ instead of $y=2^{2^x}$ and apply additive vdC.)
If we're being more careful then we should define $f:\mathbf{Z}/p\mathbf{Z}\to\mathbf{Z}/p\mathbf{Z}$ by $f(x) = 2^{\bar{x}}$, where $\bar{x}$ is the representative of $x$ satisfying $0\leq\bar{x}<p$. We're really interested in solutions to $fff(x)=x$, but using the "cocycle" relations $$f(x+y) = \begin{cases} f(x)f(y)&\text{or}\\f(x)f(y)/2,\end{cases}$$ and $$f(kx) = f(x)^k/c\text{ for some bounded }c=c_x,$$ one can reduce the problem to counting solutions to a bounded number of equations like $(\ast)$ to which the same argument applies. (I'm sure you, Helfgott, already had something like this in mind, but others may have wondered how the discontinuities could be handled.)
The equation $ffff(x)=x$ is certainly daunting. The analogue of $(\ast)$ here is, for $k=1$, $$2^{2^{y^2}} = 2^{2^y} + 1.\quad(\ast\ast)$$ Obviously $y$ and $-y$ are never both solutions to this equation, but this does not prove a $1-\epsilon$ bound because really we care about solutions $y$ to either $ff(y^2)=ff(y)+1$ or $ff(y^2/2)=ff(y)+1$, and we could well have $-y$ a solution to one whenever $y$ is a solution to the other. I don't see how to make any real progress.
[Comment from before I understood the intended question, and I thought we were counting integers $x$ in the range $0\leq x<p$ whose quadruple exponential, evaluated in $\mathbf{Z}$, is equivalent to $x\pmod{p}$: For generic $p$, the number $p-1$ will have many prime factors, which implies that $(\mathbf{Z}/(p-1)\mathbf{Z})^\times$ will surject onto $(\mathbf{Z}/2\mathbf{Z})^m$ for some large $m$. Thus not many elements of $(\mathbf{Z}/(p-1)\mathbf{Z})^\times$ are of the form $y^2$, so not many elements $x$ of $\mathbf{Z}/p\mathbf{Z}$ are even of the form $2^{y^2}$, let alone of the form $2^{2^{2^z}}$ for some integer $z \equiv x\pmod{p}$.]