I'm trying to show that $T := \mathbb{Z}/m\mathbb{Z} \otimes_{\mathbb{Z}}\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/d\mathbb{Z}$ for some $d \in \mathbb{Z}$.
Now I know that as $T$ is a tensor product, there exists a bilinear map $t : \mathbb{Z}/m\mathbb{Z} \times\mathbb{Z}/n\mathbb{Z} \rightarrow T$ such that for all Abelian groups $A$ and all bilinear maps $b : \mathbb{Z}/m\mathbb{Z} \times\mathbb{Z}/n\mathbb{Z} \rightarrow A$, there exists a unique $\tilde{b} : T \rightarrow A$ such that $b = \tilde{b} \circ t$. This is by definition of the tensor product.
I first note that for $d := \text{gcd}(m,n)$, the map
$$b :\mathbb{Z}/m\mathbb{Z} \times\mathbb{Z}/n\mathbb{Z} \rightarrow \mathbb{Z}/d\mathbb{Z}, (x \mod m, y \mod n) \mapsto xy \mod d$$
is a well-defined bilinear map. This then gives us our unique $\tilde{b}$.
Now if it were true that $(\mathbb{Z}/d\mathbb{Z}, b)$ is also a tensor product, we would obtain a map $\tilde{t}$ such that $\tilde{b} = \tilde{t}^{-1}$, hence giving a group isomorphism $T \tilde{\rightarrow} \mathbb{Z}/d\mathbb{Z}$.
To prove this, I would have to show that for every Abelian group $A$ and every bilinear map $a : \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z} \rightarrow A$, there exists a unique map $\tilde{t}: \mathbb{Z}/d\mathbb{Z} \rightarrow A$ such that $a = \tilde{t} \circ b$. Unfortunately I have no idea why that would be the case.
If you like a more algebraic approach, consider the map $$ f : \mathbb Z \to \mathbb Z / m \mathbb Z \otimes_{\mathbb Z} \mathbb Z / n \mathbb Z,\; a \mapsto a \otimes 1. $$ This is clearly surjective, so we must have $$ \mathbb Z / m \mathbb Z \otimes_{\mathbb Z} \mathbb Z / n \mathbb Z \simeq \mathbb Z / \ker f. $$ Now all that is left is to show that $\ker f$ is of the form $d \mathbb Z$. In particular if $a \in (m,n)$ then there are $k,\ell$ such that $a = km + \ell n$. Then $$ a \otimes 1 = km \otimes 1 + 1 \otimes \ell n = 0 \otimes 1 + 1 \otimes 0 = 0. $$ This shows $(m,n) \subset \ker f$. The converse is also true, so we are done.
Big edit
My "proof" essentially sidesteps using the universal property of the tensor product, and instead pushes it to the last step which I skip. I have tried to make this step rigorous but fail to do this in a nice way. So let us instead use your method.
Suppose everything in your post. In particular we have the map $a : \Bbb Z / m \Bbb Z \times \Bbb Z / n \Bbb Z \to A$. We must show that there exists a unique $\Bbb Z$-linear map $a' : \Bbb Z / d \Bbb Z \to A$ such that $a'\circ b = a$.
The tough part (I guess) is to find the map $a'$ and to recognize that $d = \gcd(m,n)$.
So let $d = \gcd(m,n)$ and define the map $$ a' : \Bbb Z / d \Bbb Z \to A,\; x \mapsto a(x,1). $$ One then shows that this map is well-defined, $\Bbb Z$-linear, satisfies $a'\circ b = a$ and unique.
Assume first that $a'$ is well-defined. The $\Bbb Z$-linearity follows immediately from the $\Bbb Z$-bilinearity of $a$. One checks that $a'\circ b(x,y) = a'(xy) = a(xy, 1) = y \cdot a(x,1) = a(x,y)$. Uniqueness can also easily be checked.
So what remains to be shown is well-definedness. Suppose $x \equiv y \mod d$, then $x - y = z \cdot d$ some $d$-multiple. Since $d = \gcd(m,n)$ there are $k,\ell$ integers such that $d = km + \ell n$. Now $$ a'(x) - a'(y) = a(x,1) - a(y,1) = a(x - y,1)\\ = a(zd,1) = a(zkm + z \ell n,1) = a(zkm,1) + a(1,z \ell n) = a(0,1) + a(1,0) = 0. $$ So $a$ is well-defined and we are done.