This is a kind of inclusion-exclusion related to the identity $$ \sum_{k=1}^m (-1)^{k+1} \binom{2m-1}{2k-1}A(2k-1)=1 \quad\quad(1) $$ for all $m=1,2,\ldots$.
For a route on the $n$-cube with first step being vertical we label other $2k-1$ vertical steps, take a weight $(-1)^{k+1}A(2k-1)$ for such a configuration and sum up. For given $k$, you may choose $2k-1$ places of vertical steps, after removing them and the first step you get a route of length $2(l-k)$. So the sum of weights of all configurations is $$\sum_{k=1}^{l}(-1)^{k+1}\binom{2l-1}{2k-1}A(2k-1)w(n,l-k).$$
On the other hand, the sum of weights of all configurations for a fixed route equals 1 due to (1). Thus the result.
You may ask how to prove (1) сombinatorially. This is most probably known, but for any sake here is a short proof.
Consider such configurations:
(i) $(x_1,\ldots,x_{2m-1})$ is a permutation of $1,\ldots,2m-1$ and $k\in \{1,\ldots,m\}$;
(ii) $2k-1$ first terms $x_1,\ldots,x_{2k-1}$ are labelled and form an alternating permutation: $x_1<x_2>x_3<\ldots >x_{2k-1}$;
(iii) other terms are decreasing: $x_{2k}>x_{2k+1}>\ldots>x_{2m-1}$.
Define the weight of such configuration as $(-1)^{k+1}$. The sum of all weights is LHS of (1) (we start with fixing $k$, next fixing the set $\{x_1,\ldots,x_{2k-1}\}$, next fix an alternating permutation on this set). On the other hand, any permutation except $\pi=(2m-1,2m-2,\ldots,1)$ is counted twice with opposite weights, and $\pi$ is counted once with weight 1.