I can get an upper bound of $C \sqrt{n} \sqrt[4]{\log n}$ and it should be possible to push this technique to get $C_l \sqrt{n} \sqrt[2l]{\log n}$ for any $l$, although Fedor's approach might be a lot simpler.

First we observe that for any positive integer $l$ we have $\text{tr } M_n^{2l} = \sum_{i=1}^{n} \lambda_i^{2l} \ge \lambda_n^{2l}$ since the eigenvalues are real, where $\lambda_1, ... \lambda_n$ are the eigenvalues of $M_n$. For $l = 1$ it's not hard to see that $\text{tr } M_n^2$ is the number of ordered pairs $(i, j)$ such that $ij \le n$, or $\sum_{i \le n} \lfloor \frac{n}{i} \rfloor = n \log n + O(n)$, which in particular certainly gives an upper bound of the form $C \sqrt{n \log n}$.

Now take $l = 2$. Then $\text{tr } M_n^4$ is the number of quadruplets $(v_1, v_2, v_3, v_4)$ such that $v_i v_{i+1} \le n$ in cyclic order. We distinguish three cases.

**Case:** $v_1 = k > v_3$. Then $v_2, v_4$ can be any positive integers less than or equal to $\left\lfloor \frac{n}{k} \right\rfloor$ and $v_3$ can be any positive integer less than $k$, which gives

$$\sum_{k \le n} \left\lfloor \frac{n}{k} \right\rfloor^2 (k-1) = n^2 \log n + O(n^2)$$

quadruplets.

**Case:** $v_1 = k = v_3$. There are $O(n^2)$ possibilities here.

**Case:** $v_1 = k < v_3$. Same number as the first case by symmetry.

This gives $\text{tr } M_n^4 = 2n^2 \log n + O(n^2)$. Again, I think this argument can be pushed further.

**Edit:** We can argue similarly for $l = 3$. We are now counting sextuplets $(v_1, ... v_6)$. The triplet $(v_1, v_3, v_5)$ can be in one of six possible orders (discounting the cases where some of them are equal, which I think is $O(n^3)$), all of which can be reached from each other by cyclic permutation and reflection, so WLOG $v_1 \ge v_3 \ge v_5$. Then $v_2, v_6$ can be any positive integers less than or equal to $\lfloor \frac{n}{v_1} \rfloor$ while $v_4$ can be any positive integer less than or equal to $\lfloor \frac{n}{v_3} \rfloor$ and $v_5$ can be any positive integer less than or equal to $v_3$, which gives

$$\sum_{n \ge v_1 \ge v_3} \left\lfloor \frac{n}{v_1} \right\rfloor^2 \left\lfloor \frac{n}{v_3} \right\rfloor v_3 = n^3 \sum_{n \ge v_1 \ge v_3} \frac{1}{v_1^2} + O(n^3) = n^3 \log n + O(n^3)$$

sextuplets. Our WLOG assumption overcounts by a factor of $6$ (up to an error of size $O(n^3)$), which gives $\text{tr } M_n^6 = 6n^3 \log n + O(n^3)$ and an upper bound of $C \sqrt{n} \sqrt[6]{\log n}$.