I'll post a partial answer.
Pretend your functions are given by Taylor series to the needed (second) order.
So, we write
$$x_p=h_p(y)=\sum \frac{\partial h_p}{\partial y_k} y_k + \sum_{i,j} \frac{1}{2}\frac{\partial^2 h_p}{\partial y_i \partial y_j} y_i y_j$$
$$\Phi_l(x,y)= \sum_k \frac{\partial \Phi_l}{\partial x_k} x_k + \sum_p \frac{\partial \Phi_l}{\partial y_p} y_p + \sum_{i,j} \frac{1}{2}\frac{\partial^2 \Phi_l}{\partial x_i \partial x_j} x_i x_j+ \sum_{q,r} \frac{1}{2}\frac{\partial^2 \Phi_l}{\partial y_q \partial y_r} y_q y_r+\sum_{p,k} \frac{1}{2} \frac{\partial^2 \Phi_l}{\partial y_p \partial x_k} y_p x_k+
\sum_{p,k} \frac{1}{2} \frac{\partial^2 \Phi_l}{\partial x_k \partial y_p} x_k y_p $$
Now plug in and keep equate the coefficients of $y_i y_j$ to zero. There are 5 terms in $\Phi_l$. They contribute (in the case of $i\neq j$, so summing the "$y_iy_j$" and the "$y_jy_i$" contributions; there are 1/2 factors throughout if $i=j$):
1) Nothing.
2) $\sum_p \frac{\partial \Phi_l}{\partial y_p} \frac{\partial^2 h_p}{\partial y_i \partial y_j} $
3) $\frac{\partial^2 \Phi_l}{\partial y_i \partial y_j}$
4)$ \sum_{q,r} \frac{\partial^2 \Phi_l}{\partial x_q \partial x_r} \frac{\partial h_q}{\partial y_i} \frac{\partial h_r}{\partial y_j}$
5)$\sum_{p} \frac{\partial^2 \Phi_l}{\partial x_p \partial y_j} \frac{\partial h_p}{\partial y_i} $
6)$\sum_{p} \frac{\partial^2 \Phi_l}{ \partial y_i \partial y_p} \frac{\partial h_p}{\partial y_j} $
Varying $l$, one gets $n$ linear equations (labeled by $l$) in $n$ unknowns $\frac{\partial^2 h_p}{\partial y_i \partial y_j} $ (labeled by $p$), which can therefore be written as $A z=b$, with the matrix $A$ of the linear system given by $\Phi_{x}$. Hence these equations can be solved. The only trouble is in writing the $b$ vector, which is the sum of terms 3-6, in a "vector" format.
Maybe a better way to do bookkeeping for this is to use tree-speak like here...
To show that $\dfrac{\partial^2 E_x}{\partial s \partial q}=0$ compute the second partial derivatives in the original PDE, $\dfrac{\partial^2 E_x}{\partial t^2}-c^2\dfrac{\partial^2 E_x}{\partial z^2}=0$ in terms of the partial derivatives wrt to the new variables. In fact, you did it half the way as you did it for the first derivatives,
$$\frac{\partial E_x}{\partial z}=\frac{\partial E_x}{\partial s}+\frac{\partial E_x}{\partial q}$$
and
$$\frac{\partial E_x}{\partial t}=c\biggl(\frac{\partial E_x}{\partial s}-\frac{\partial E_x}{\partial q}\biggr)\tag{b}$$
So,
$$\frac{\partial^2 E_x}{\partial z^2}=\left(\frac{\partial }{\partial s}+\frac{\partial}{\partial q}\right)\left(\frac{\partial E_x}{\partial s}+\frac{\partial E_x}{\partial q}\right)=\left(\frac{\partial^2 E_x}{\partial s^2}+2\frac{\partial^2 E_x}{\partial q \partial s}+\frac{\partial^2 E_x}{\partial q^2}\right)$$
and
$$\frac{\partial^2 E_x}{\partial t^2}=c\left(\frac{\partial }{\partial s}-\frac{\partial}{\partial q}\right)c\left(\frac{\partial E_x}{\partial s}-\frac{\partial E_x}{\partial q}\right)=c^2\left(\frac{\partial^2 E_x}{\partial s^2}-2\frac{\partial^2 E_x}{\partial q \partial s}+\frac{\partial^2 E_x}{\partial q^2}\right)$$
Substituting:
$$0=\dfrac{\partial^2 E_x}{\partial t^2}-c^2\dfrac{\partial^2 E_x}{\partial z^2}=c^2\left(\frac{\partial^2 E_x}{\partial s^2}-2\frac{\partial^2 E_x}{\partial q \partial s}+\frac{\partial^2 E_x}{\partial q^2}\right)-c^2\left(\frac{\partial^2 E_x}{\partial s^2}+2\frac{\partial^2 E_x}{\partial q \partial s}+\frac{\partial^2 E_x}{\partial q^2}\right)=$$
$$=-4c^2\frac{\partial^2 E_x}{\partial q \partial s}$$
which means,
$$\frac{\partial^2 E_x}{\partial q \partial s}=0$$
Best Answer
The key here isn't the Leibniz rule but the multivariable chain rule. Let $$ F(x) := \int_0^x \int_0^x f(s,t) \,ds\,dt, $$ and observe that $$ F(x) = G(x,x), \quad G(u,v) := \int_0^v \int_0^u f(s,t) \,ds\,dt. $$ In other words, $F(x) = G(u(x),v(x))$ for $u(x) = x$ and $v(x) = x$. Thus, by a first application of the multivariable chain rule, $$ F^\prime(x) = \frac{\partial G}{\partial u}\frac{d u}{d x} + \frac{\partial G}{\partial v}\frac{d v}{d x} = \frac{\partial G}{\partial u}(u(x),v(x)) + \frac{\partial G}{\partial v}(u(x),v(x)), $$ and hence, by a second application of the multivariable chain rule, $$ F^{\prime\prime}(x) = \left(\frac{\partial}{\partial u}\left(\frac{\partial G}{\partial u}\right)\frac{du}{dx} +\frac{\partial}{\partial v}\left(\frac{\partial G}{\partial u}\right)\frac{dv}{dx} \right) + \left(\frac{\partial}{\partial u}\left(\frac{\partial G}{\partial v}\right)\frac{du}{dx} +\frac{\partial}{\partial v}\left(\frac{\partial G}{\partial v}\right)\frac{dv}{dx} \right)\\ = \frac{\partial^2 G}{\partial u^2}(u(x),v(x)) + \frac{\partial^2 G}{\partial v\partial u}(u(x),v(x)) + \frac{\partial^2 G}{\partial u \partial v}(u(x),v(x)) + \frac{\partial^2 G}{\partial v^2}(u(x),v(x))\\ = \frac{\partial^2 G}{\partial u^2}(x,x) + \frac{\partial^2 G}{\partial v\partial u}(x,x) + \frac{\partial^2 G}{\partial u \partial v}(x,x) + \frac{\partial^2 G}{\partial v^2}(x,x). $$ At this point, all you need to do is compute the second-order partial derivatives of $G(u,v)$, but this is now a fairly straightforward exercise in applying the fundamental theorem of calculus, one variable at a time.