It might be helpful to first show $\operatorname{hom}_\mathbb{Z}(\mathbb{Z}_{p^\ell},\mathbb{Z}_{p^k})\simeq\mathbb{Z}_{p^{\min\{\ell,k\}}}$.
Using your notation, denote elements of $\mathbb{Z}_{p^\ell}$ and $\mathbb{Z}_{p^k}$ by $[\cdot]_\ell$ and $[\cdot]_k$, respectively. Then define
$$
f_{[\cdot]_k}\colon \mathbb{Z}_{p^\ell}\to\mathbb{Z}_{p^k}:[a]_\ell\mapsto a[x]_k.
$$
Let $X=\{f_{[x]_k}:\operatorname{ord}([x]_k)\mid p^\ell\}$. I claim that $X=\operatorname{hom}_\mathbb{Z}(\mathbb{Z}_{p^\ell},\mathbb{Z}_{p^k})$. First, take $f_{[x]_k}\in X$. To see it is well defined, suppose $[a]_\ell=[b]_\ell$, so that $p^\ell\mid a-b$. Then
$$
f_{[x]_k}([a]_\ell)-f_{[x]_k}([b]_\ell)=a[x]_k-b[x]_k=(a-b)[x]_k=0
$$
since $\operatorname{ord}([x]_k)\mid p^\ell$, and hence also divides $a-b$. Further, $f_{[x]_k}$ is also a homomorphism, since
\begin{align*}
f_{[x]_k}([a]_\ell+[b]_\ell) &= f_{[x]_k}([a+b]_\ell)\\
&= (a+b)[x]_k\\
&= a[x]_k+b[x]_k\\
&= f_{[x]_k}([a]_\ell)+f_{[x]_k}([b]_\ell).
\end{align*}
Conversely, Take $f\in\operatorname{hom}_\mathbb{Z}(\mathbb{Z}_{p^\ell},\mathbb{Z}_{p^k})$. For any $[a]_\ell\in\mathbb{Z}_{p^\ell}$,
$$
f([a]_\ell)=f(a[1]_\ell)=af([1]_\ell)
$$
and thus $f=f_{f[1]_\ell}$ and since $\operatorname{ord}(f[1]_\ell)\mid\operatorname{ord}[1]_\ell=p^\ell$, and so $f\in X$ and set equality follows.
I now claim $\vert X\vert=p^{\min\{\ell,k\}}$. This is equivalent to counting the number of elements of $\mathbb{Z}_{p^k}$ with order dividing $p^\ell$. If $k\leq\ell$, it follows that there are $p^k$ such elements by Lagrange's theorem. If $\ell\leq k$, then recall from group theory that $[x]_k=x[1]_k$ as order $p^k/(p^k,x)$. This divides $p^\ell$ if and only if $(p^k,x)/p^{k-\ell}$ is an integer. This occurs if and only if $p^{k-\ell}\mid x$, and there are $p^\ell$ such element in $\mathbb{Z}_{p^k}$ since we can take $x=p^{k-\ell}\cdot c$ for $c=1,\dots,p^\ell$. In either case, $\vert X\vert=p^{\min\{k,\ell\}}$.
I now claim $\operatorname{ord}([x]_k)=\operatorname{ord}(f_{[x]_k})$, viewing $X$ as an additive group. Observe
$$
0=\operatorname{ord}(f_{[x]_k})f_{[x]_k}([a]_\ell)=\operatorname{ord}(f_{[x]_k})a[x]_k
$$
for all $a$. So for $a=1$, we conclude $\operatorname{ord}([x]_k)\leq\operatorname{ord}(f_{[x]_k})$. Also,
$$
\operatorname{ord}([x]_k)f_{[x]_k}([a]_\ell)=\operatorname{ord}([x]_k)\cdot a[x]_k=0
$$
so $\operatorname{ord}(f_{[x]_k})\leq\operatorname{ord}([x]_k)$. Now $[p^{k-\min\{\ell,k\}}]_k$ has order $\min\{\ell,k\}$, and thus the corresponding element of $X$ does, and so $X\simeq \mathbb{Z}_{p^{\min\{\ell,k\}}}$.
Also, observe that $\operatorname{hom}_\mathbb{Z}(\mathbb{Z}_{p^i},\mathbb{Z}_{q^j})\simeq\{0\}$ if $p\neq q$, since the image of any element under a homomorphism must then divide $p^i$ and $q^j$, and thus has order $1$, from which it follows that the only homomorphism between the two groups is the trivial homomorphism.
Now you can adapt this to arbitrary $m$ and $n$.
So write $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ and $m=p_1^{\beta_1}\cdots p_k^{\beta_k}$, where the exponents may be $0$. Then recalling how the $\operatorname{hom}$ functor splits over products and direct sums, which can be found in Lang's Algebra, Chapter III, Section $3$, we have
\begin{align*}
\operatorname{hom}_\mathbb{Z}(\mathbb{Z}_n,\mathbb{Z}_m)&\simeq \operatorname{hom}_\mathbb{Z}\left(\prod_{i=1}^k\mathbb{Z}_{p_i^{\alpha_i}},\prod_{j=1}^k\mathbb{Z}_{p_j^{\beta_j}}\right)\\
&\simeq \prod_{i,j=1}^k\operatorname{hom}_\mathbb{Z}\left(\mathbb{Z}_{p_i^{\alpha_i}},\mathbb{Z}_{p_j^{\beta_j}}\right)\\
&\simeq \prod_{\ell=1}^k\operatorname{hom}_\mathbb{Z}\left(\mathbb{Z}_{p_\ell^{\alpha_\ell}},\mathbb{Z}_{p_\ell^{\beta_\ell}}\right)\\
&\simeq \prod_{\ell=1}^k\mathbb{Z}_{p_\ell^{\min\{\alpha_\ell,\beta_\ell\}}}\\
&\simeq \mathbb{Z}_{p_1^{\min\{\alpha_1,\beta_1\}}\cdots p_k^{\min\{\alpha_k,\beta_k\}}}\\
&=\mathbb{Z}_{(n,m)}.
\end{align*}
(I read this proof a few years back while studying group theory, and TeXed it up. I can't recall the original source however, apologies!)
