, 2019

The required maximum is $\binom{m-1}{2}n^2$, and is achieved if, for instance
$$A_k = \{a^{(k-1)n+1}, a^{(k-1)n+2}, \dots, a^{kn}\}, \quad k = 1, \dots, m-1,$$

For brevity, an ordered pair $(a, b)$ satisfying the conditions in the statement will be called suitable. We show that the number of suitable pairs does not exceed $\binom{m-1}{2}n^2$.
For every $m$-tuple $(a_1, \dots, a_m)$, where $a_k$ is a member of $A_k$, $k = 1, \dots, m$, let $k(a_1, \dots, a_m)$ be the number of suitable pairs $(a_i, a_j)$ it contains.
We show by induction on $m$ that $k(a_1, \dots, a_m) \le \binom{m-1}{2}$. Since there are exactly $n^m$ $m$-tuples, and each suitable pair is contained in exactly $n^{m-2}$ such, the conclusion follows.
The case $m = 3$ is easily dealt with. Let $m \ge 4$ and fix an $m$-tuple $(a_1, \dots, a_m)$,
$a_k \in A_k$, $k = 1, \dots, m$; without loss of generality, we may and will assume that
$a_1$ is the largest entry. The $(m-1)$-tuple $(a_1, \dots, a_{m-1})$ then satisfies the induction
hypothesis: $a_2$ does not divide $a_1$, $a_3$ does not divide $a_2$, and so on and so forth, $a_{m-1}$
does not divide $a_{m-2}$, and, by maximality, $a_1$ does not divide $a_{m-1}$.
We show that the number of suitable pairs containing $a_m$ does not exceed $m-2$.
It then follows that $k(a_1, \dots, a_m) \le k(a_1, \dots, a_{m-1}) + m-2 \le \binom{m-2}{2} + m-2 =
\binom{m-1}{2}$, as desired.
Notice that, for each $k$ in the range $1$ through $m-1$, at most one of the pairs
$(a_k, a_m)$, $(a_m, a_k)$ is suitable. If neither $(a_k, a_m)$ nor $(a_m, a_k)$ is suitable for some $k$,
then the number of suitable pairs containing $a_m$ is clearly at most $m-2$. Otherwise,
since the pairs $(a_m, a_k)$ and $(a_{k+1}, a_m)$, $k = 1, \dots, m-2$, are not simultaneously
suitable, and the pair $(a_1, a_m)$ is certainly not suitable, by maximality of $a_1$, it follows
that the pairs $(a_m, a_k)$, $k = 1, \dots, m-1$, are all suitable, contradicting the fact that
$a_m$ does not divide $a_{m-1}$. This ends the proof.