A sum of fractional parts.
Solution 1:
Let's call your sum $f(m,n)$. The ordinary generating function of $f(\cdot,n)$ appears to be of the form $$g(z,n) = \frac{z^2 p_n(z)}{6 (1-z)(1-z^n)}$$ where $p_n$ is a polynomial of degree $n-1$ (except for $n=2$ where it has degree $0$): $$\eqalign{ p_{{2}}&=3\cr p_{{3}}&=-{z}^{2}+7\,z+3\cr p_{{4}}&=-3\,{z}^{3}+12\,{z}^{2}+3\,z+6\cr p_{{5}}&=-6\,{z}^{4}+18\,{z}^{3}+6\,{z}^{2}+6\,z+6\cr p_{{6}}&=-10\,{z}^{5}+25\,{z}^{4}+6\,{z}^{3}+5\,{z}^{2}+10\,z+9\cr p_{{7}}&=-15\,{z}^{6}+33\,{z}^{5}+9\,{z}^{4}+9\,{z}^{3}+9\,{z}^{2}+9\,z +9\cr p_{{8}}&=-21\,{z}^{7}+42\,{z}^{6}+9\,{z}^{5}+12\,{z}^{4}+3\,{z}^{3}+18 \,{z}^{2}+9\,z+12\cr p_{{9}}&=-28\,{z}^{8}+52\,{z}^{7}+12\,{z}^{6}+8\,{z}^{5}+16\,{z}^{4}+12 \,{z}^{3}+8\,{z}^{2}+16\,z+12\cr p_{{10}}&=-36\,{z}^{9}+63\,{z}^{8}+12\,{z}^{7}+15\,{z}^{6}+12\,{z}^{5}+ 3\,{z}^{4}+24\,{z}^{3}+15\,{z}^{2}+12\,z+15\cr p_{{11}}&=-45\,{z}^{10}+75\,{z}^{9}+15\,{z}^{8}+15\,{z}^{7}+15\,{z}^{6} +15\,{z}^{5}+15\,{z}^{4}+15\,{z}^{3}+15\,{z}^{2}+15\,z+15\cr p_{{12}}&=-55\,{z}^{11}+88\,{z}^{10}+15\,{z}^{9}+14\,{z}^{8}+13\,{z}^{7 }+24\,{z}^{6}-{z}^{5}+34\,{z}^{4}+9\,{z}^{3}+20\,{z}^{2}+19\,z+18\cr}$$
EDIT: This seems to come from the fact that $$f(m+n,n) - f(m,n) =\frac{n^2-n}{4}$$ for all $m$ and $n$.
EDIT: Let $g(m,n) = f(m,n) - \dfrac{(m-1)(n-1)}{4}$. From $f(m+n,n) - f(m,n) = \dfrac{n^2-n}{4}$ we get $g(m+n,n) = g(m,n)$. By following the Euclidean algorithm, we get $$g(m,n) = g(d,d) = \dfrac{(d-1)(2d-1)}{6} - \dfrac{(d-1)^2}{4} = \frac{d^2-1}{12}$$ where $d = \gcd(m,n)$. That is, $$ f(m,n) = \frac{\gcd(m,n)^2-1}{12} + \dfrac{(m-1)(n-1)}{4} $$
Solution 2:
Analysis of a small example $m=4, n=6$ with $d=\mathrm{gcd}(4,6)=2$ indicates how to derive the general case.
\begin{align*} \sum_{1\leq k\leq 24}&\left\{\frac{k}{4}\right\}\left\{\frac{k}{6}\right\}\\ &=\color{blue}{\frac{1}{4}\cdot\frac{1}{6}+\frac{2}{4}\cdot\frac{2}{6}+\frac{3}{4}\cdot\frac{3}{6} +\frac{0}{4}\cdot\frac{4}{6}+\frac{1}{4}\cdot\frac{5}{6}+\frac{2}{4}\cdot\frac{0}{6}}\\ &\,\,\qquad\color{blue}{+\frac{3}{4}\cdot\frac{1}{6}+\frac{0}{4}\cdot\frac{2}{6}+\frac{1}{4}\cdot\frac{3}{6} +\frac{2}{4}\cdot\frac{4}{6}+\frac{3}{4}\cdot\frac{5}{6}+\frac{0}{4}\cdot\frac{0}{6}}\\ &\qquad+\frac{1}{4}\cdot\frac{1}{6}+\frac{2}{4}\cdot\frac{2}{6}+\frac{3}{4}\cdot\frac{3}{6} +\frac{0}{4}\cdot\frac{4}{6}+\frac{1}{4}\cdot\frac{5}{6}+\frac{2}{4}\cdot\frac{0}{6}\\ &\qquad+\frac{3}{4}\cdot\frac{1}{6}+\frac{0}{4}\cdot\frac{2}{6}+\frac{1}{4}\cdot\frac{3}{6} +\frac{2}{4}\cdot\frac{4}{6}+\frac{3}{4}\cdot\frac{5}{6}+\frac{0}{4}\cdot\frac{0}{6}\\ &=2\left(\frac{1}{4}\cdot\frac{1}{6}\color{blue}{+\frac{2}{4}\cdot\frac{2}{6}}+\frac{3}{4}\cdot\frac{3}{6} \color{blue}{+\frac{0}{4}\cdot\frac{4}{6}}+\frac{1}{4}\cdot\frac{5}{6}\color{blue}{+\frac{2}{4}\cdot\frac{0}{6}}\right.\\ &\qquad\left.+\frac{3}{4}\cdot\frac{1}{6}\color{blue}{+\frac{0}{4}\cdot\frac{2}{6}}+\frac{1}{4}\cdot\frac{3}{6} \color{blue}{+\frac{2}{4}\cdot\frac{4}{6}}+\frac{3}{4}\cdot\frac{5}{6}\color{blue}{+\frac{0}{4}\cdot\frac{0}{6}}\right)\tag{1}\\ &=2\left(\frac{0}{4}+\frac{2}{4}\right)\left(\frac{0}{6}+\frac{2}{6}+\frac{4}{6}\right) +2\left(\frac{1}{4}+\frac{3}{4}\right)\left(\frac{1}{6}+\frac{3}{6}+\frac{5}{6}\right)\tag{2} \end{align*}
Generalising these steps we obtain for non-negative integers $m,n$ and $d=\mathrm{gcd}(m,n)$ \begin{align*} &\color{blue}{\sum_{1\leq k\leq mn}}\color{blue}{\left\{\frac{k}{m}\right\}\left\{\frac{k}{n}\right\}}\\ &\quad=d\sum_{k=1}^{\frac{mn}{d}}\left\{\frac{k}{m}\right\}\left\{\frac{k}{n}\right\}\tag{3}\\ &\quad=d\sum_{j=0}^{d-1}\left(\sum_{p=0}^{\frac{m}{d}-1}\frac{j+pd}{m}\right) \left(\sum_{q=0}^{\frac{n}{d}-1}\frac{j+qd}{n}\right)\tag{4}\\ &\quad=d\sum_{j=0}^{d-1}\left(\frac{m}{d}\cdot\frac{j}{m}+\frac{d}{m}\cdot\frac{1}{2}\left(\frac{m}{d}-1\right)\frac{m}{d}\right) \left(\frac{n}{d}\cdot\frac{j}{n}+\frac{d}{n}\cdot\frac{1}{2}\left(\frac{n}{d}-1\right)\frac{n}{d}\right)\tag{5}\\ &\quad=d\sum_{j=0}^{d-1}\left(\frac{j}{d}+\frac{1}{2}\left(\frac{m}{d}-1\right)\right) \left(\frac{j}{d}+\frac{1}{2}\left(\frac{n}{d}-1\right)\right)\\ &\quad=d\left(\frac{1}{d^2}\cdot\frac{1}{6}(d-1)d(2d-1) +\frac{1}{2}\cdot\left(\frac{m}{d}-1\right)\frac{1}{d}\cdot\frac{1}{2}(d-1)d\right.\\ &\qquad\left.+\frac{1}{2}\cdot\left(\frac{n}{d}-1\right)\frac{1}{d}\cdot\frac{1}{2}(d-1)d +\frac{1}{4}\left(\frac{m}{d}-1\right)\left(\frac{n}{d}-1\right)\right)\tag{6}\\ &\quad=\frac{1}{6}(d-1)(2d-1)+\frac{1}{4}(m-d)(d-1)\\ &\qquad +\frac{1}{4}(n-d)(d-1)+\frac{1}{4}(m-d)(n-d)\\ &\quad\,\,\color{blue}{=\frac{1}{4}(m-1)(n-1)+\frac{1}{12}\left(d^2-1\right)} \end{align*}
Comment:
In (3) we use as in (1) that the $mn$ summands are $d=gcd(m,n)$ copies of the first $\frac{mn}{d}$ summands.
In (4) we see correspondingly to (2) in groups of $\frac{mn}{d}$ elements $d$ copies of size $\frac{m}{d}\cdot\frac{n}{d}$.
In (5) we calculate the inner sums using $\sum_{j=0}^n j=\frac{1}{2}n(n+1)$ and $\sum_{j=0}^n j^2=\frac{1}{6}n(n+1)(2n+1)$.
In (6) we calculate the outer sum using the summation formulas as in (5).