We show that for all $m, n \geq 2$ the polynomial $f_n \left( x^m \right)$ is irreducible.
This answer is based on a wonderful technique I learnt a few years ago from an answer on MSE by Keith Conrad, and I encourage the reader to look at that answer first (it is not very long), as it shows the key ideas in a much nicer setup. I do here a lot of casework which can probably be shortened, but I didn't really attempt to streamline it. If
$$p(x) = \sum_{i = 0}^{n} a_i x^i$$
is a polynomial of degree $n$, then we define
$$\tilde{p} (x) = \sum_{i = 0}^{n} a_{n - i} x^i$$
that is the polynomial with coefficients reversed. Algebraically, $\tilde{p} (x) = x^{\mathrm{deg} (P)} p \left( \frac{1}{x} \right)$. Notice that
$$(x - 1) f_n (x) = x^{n + 1} - 2 x^n + 1$$
Therefore, to understand the factorization of $f_n \left( x^m \right)$, it suffices to understand the factorization of
$$x^{n m + m} - 2 x^{n m} + 1$$
Fix $n, m$ and from now on we will call this polynomial $f(x)$. Throughout, we will assume that $n > 2$: if $n = 2$ the method that we use shows that for all $m$ the polynomial $f_{n} \left( x^m \right)$ is irreducible.
Suppose that there was a factorization into nonconstant monic polynomials $g, h$
$$f = g h$$
Then, taking $k = g \tilde{h}$ or $k = - g \tilde{h}$ (according to whether $g(0) = 1$ or $- 1$ respectively), we see that $k$ is a monic polynomial such that
$$f \tilde{f} = k \tilde{k}$$
We will show that this implies that $k = f$ or $k = \tilde{f}$. Write
$$k(x) = \sum_{i = 0}^{n m + m} a_i x^i$$
and then
$$\tilde{k} (x) = \sum_{i = 0}^{n m + m} a_{n m + m - i} x^i$$
We know that $a_{n m + m} = 1$, and by looking at the constant coefficient of $k \tilde{k} = f \tilde{f}$ we see that $a_0 = 1$. Now, the key point: compare the coefficient of $x^{n m + m}$ in $f \tilde{f} = k \tilde{k}$: it is the sum of the squares of the coefficients of $f$ and $k$ respectively, therefore
$$\sum_{i = 0}^{n m + m} a_{i}^2 = 6$$
It will be useful in the cases below to see explicitly what $f \tilde{f}$ is:
$$f \tilde{f} = x^{2 m n + 2 m} - 2 x^{2 m n + m} - 2 x^{m n + 2 m} + 6 x^{m n + m} - 2 x^{m n} - 2 x^{m} + 1$$
From the coefficients of $k$ we already now, there are two possibilities:
Case 1: There exist $m n + m > a > b > c > d > 0$ such that
$$k(x) = x^{n m + m} \pm x^a \pm x^b \pm x^c \pm x^d + 1$$
Looking at the coefficient of $x^{2 n m + 2 m - 1}$ in $k \tilde{k}$ we see that we must have $a = n m + m - 1, \ d = 1$ and $x^a, x^d$ must both come with a minus sign. We must have $k(1) = 0$, and so without loss of generality (otherwise we look at $\tilde{k}$) $x^b$ comes with a plus sign and $x^c$ with a minus. Now,
$$k \tilde{k} = \left( x^{m n + m} - x^{m n} + x^b - x^c - x^m + 1 \right) \times \\ \left( x^{m n + m} - x^{m n} - x^{m n + m - c} + x^{m n + m - b} - x^m + 1 \right)$$
Looking at the coefficient of $x^{2 m n}$, since $n > 2$ the positive contribution of $\left( - x^{m n} \right) \left( x^{- m n} \right)$ must cancel out, and the only options are $c = 2 m, m n - m$. In particular $c$ is divisible by $m$. Substituting $x$ to be a primitive $m$-th root of unity, we get that $x^b = 1$, and therefore $b$ is divisible by $m$ as well. Since $m n > b > c$, this rules out the option of $c$ being $m n - m$, and therefore we have $c = 2 m$. Now looking at the coefficient of $x^{m n}$ we see that we must have $b = m n - m$, but this means that the coefficient of $x^{2 m n}$ is wrong, and so we get a contradiction. Therefore, what happens is
Case 2: for some $m n + m > a > 0$, we have $k(x) = x^{m n + m} \pm 2 x^a + 1$. It is immediate to see in this case that $a = mn, m$ and $x^a$ comes with a minus sign, that is $k = f, \tilde{f}$ and without loss of generality, $k = f$.
Therefore $g h = \pm g \tilde{h}$, that is $h = \pm \tilde{h}$. However, notice that
$$\gcd \left( f, \tilde{f} \right) = \gcd \left( x^{m n + m} - 2 x^{m n} + 1, x^{m n - m} - 1 \right) = \\ = \gcd \left( x^{2 m} - 2 x^{m} + 1, x^{m n - m} - 1 \right)$$
It is easy to see that the only roots of $x^{2 m} - 2 x^m + 1$ which are on the unit circle are the $m$-th roots of unity, and they each appear with multiplicity $1$, therefore $\gcd \left( f, \tilde{f} \right) = x^m - 1$. Since $h | f, \ \tilde{h} | \tilde{f}$ we have $h | \gcd \left( f, \tilde{f} \right) = x^m - 1$.
Over all, we have shown that in every nontrivial factorization of $\left( x^m - 1 \right) f_n \left( x^m \right) = g h$, one of the factors on the right hand side divides $x^m - 1$, which immediately implies that $f_n \left( x^m \right)$ is irreducible: if there was a factorization $f_n \left( x^m \right) = u(x) v(x)$ then $g(x) = u(x), \ h(x) = \left( x^m - 1 \right) v(x)$ would be a counterexample. QED