Combinatorial interpretation
Let's start with a combinatorial interpretation of $\Delta(A)_{i,j}$. It is a weighted sum of terms, each of which corresponds to a directed $1$-regular graph. Each term is the product of the corresponding entries of $A$, only we don't count the $(j,i)$ edge. In other words, the graph is not really $1$-regular, since $i$ has no in-edge and $j$ has no out-edge; so there is an $i$ to $j$ path, and the rest are circles. Each term is weighted according to the sum of the permutation.
Multiplicativity
Now $\Delta(AB)_{i,j}$ is the same thing, only each $(x,y)$ edge really corresponds to a pair of edges $(x,z),(z,y)$, with $z$ arbitrary. Suppose a vertex $z$ appears twice, in both $(x_1,z),(z,y_1)$ and $(x_2,z),(z,y_2)$. Replace this wiring to the wiring $(x_1,z),(z,y_2)$ and $(x_2,z),(z,y_1)$. This corresponds to a transposition, and so the sign is opposite and the two cancel. We are left with only the terms where each vertex appears at most once as an intermediate.
Similarly, in $(\Delta(A)\Delta(B))_{i,j}$ we have two graphs superimposed, with an $i$ to $j$ path composed of an $A$ part followed by a $B$ part. We can now construct a $\Delta(AB)_{i,j}$ path in the obvious way; this is a reversible process (the missing $z$ vertex is the one in the middle of the $i$ to $j$ path). Since sign is multiplicative, the signs agree.
Involution up to scaling
Consider now $(\Delta(\Delta(A))_{i,j}$. On the first level, we have an almost $1$-regular graph, with some $i$ to $j$ path. On the second level, each edge $x,y$ on the first level corresponds to some $1$-regular graph with some $x$ to $y$ path.
Let's count the in- and out-degrees of all the vertices. We start with $n-1$ each. For each edge $(x,y)$, remove $1$ from the in-degree of $x$, and $1$ from the out-degree of $y$. Every vertex other than $i$ has an incoming edge, and every vertex other than $j$ has an outgoing edge. Let's assume that $i \neq j$ (the other case is simpler). Thus the out-degree of $i$ is $n-1$, and of every other vertex it is $n-2$; the in-degree of $j$ is $n-1$, and of every other vertex it is $n-2$.
Suppose the path from $i$ to $j$ is not direct, for example $i$ goes to $k$ goes to $l$ (which might equal $j$). It is possible that if you're cunning enough, you will be able to permute $k$ and $j$ in such a way that the result will have the same value but opposite sign. Given that, we are left only with terms in which the $i$ to $j$ path is direct. The rest of the multigraph is just an arbitrary $(n-2)$-regular graph, which explains the factor $(\det A)^{n-2}$.
It remains for someone in the audience to find the correct cut-and-paste argument...
Best Answer
That there exists a minor of order $n$ which is non-zero suggests that there exists at least $n$ linearly independent rows/columns of the matrix (namely the rows/columns of the submatrix corresponding to the minor). The rank is thus at least $n$. If the rank is larger than $n$ then there exists at least $n+1$ linearly independent rows, meaning the $n+1$ order submatrix taken using those rows will be invertible and have non-zero determinant contrary to the fact that the all $n+1$ order minors are zero. This shows that the rank must be $n$.
Edit: As Jyrki pointed out, only the minors which contain $m_n$ are zero. So let us proceed another way. The whole matrix cannot have full rank since it must contain $m_n$. That means there is at least one linearly dependent row and column which is not in $m_n$ since all rows and columns in $m_n$ are linearly independent. Removing the row and the column produces a smaller matrix which again contains $m_n$. We can repeat this procedure until all that remains is $m_n$, proving the rank is $n$.