What is the connection between sum of tuple products and permutations by cycle?

This is very classical material, closely related to Newton's identities for the elementary and the power sum symmetric functions; that keyword will bring up a lot of references. I like Chapter 7 of Stanley's Enumerative Combinatorics, Vol. II but be warned that it has a lot of material.

Here is a short but maybe unsatisfying proof. Your functions $f_m$ are more commonly known as the elementary symmetric functions and denoted $e_m$. Your functions $S_k$ are more commonly known as the power sum symmetric functions and denoted $p_k$. The elementary symmetric functions have generating function

$$E(t) = \sum_{k=0}^n e_k t^k = \prod_{i=1}^n (1 + tx_i)$$

whereas the power sum symmetric functions have generating function

$$P(t) = \sum_{k=0}^{\infty} p_k t^k = \sum_{i=1}^n \frac{1}{1 - tx_i}.$$

These generating functions can be related by the logarithmic derivative, which gives

$$\log E(t) = \sum_{i=1}^n \log (1 + tx_i)$$

and hence

$$\frac{d}{dt} \log E(t) = \sum_{i=1}^n \frac{x_i}{1 + tx_i} = \sum_{k=0}^{\infty} (-1)^k p_{k+1} t^k.$$

Integrating both sides gives

$$\log E(t) = \sum_{k=1}^{\infty} (-1)^{k-1} \frac{p_k}{k} t^k$$

and exponentiating gives

$$E(t) = \exp \left( \sum_{k=1}^{\infty} (-1)^{k-1} \frac{p_k}{k} t^k \right).$$

Expanding this out completely gives an identity relating $e_k$ and $p_k$ in terms of sums over permutations, generalizing the ones you gave, by the permutation form of the exponential formula. It can be stated succinctly as follows: if $\sigma \in S_n$ is a permutation, write $\text{sgn}(\sigma)$ for its signature, and write $p_{\sigma} = \prod_{i=1}^n p_i^{c_i(\sigma)}$ where $c_i(\sigma)$ is the number of $i$-cycles of $\sigma$. Then

$$\boxed{ e_n = \frac{1}{n!} \sum_{\sigma \in S_n} \text{sgn}(\sigma) p_{\sigma} }.$$

Some years ago I tried to work out a purely combinatorial proof of an equivalent version of this identity involving the complete homogeneous symmetric polynomials $h_k$, namely

$$h_n = \frac{1}{n!} \sum_{\sigma \in S_n} p_{\sigma}$$

which is equivalent to the previous one via the substitution $t \mapsto -t$ in the generating function. You can see how far I got in my blog post Newton's sums, necklace congruences, and Zeta functions II; there it's stated somewhat indirectly in terms of walks on graphs (the $x_i$ correspond to the eigenvalues of the graph) and it could be cleaned up to work in terms of the $x_i$ directly. I haven't tried to push through an argument for the $e_k$ version involving inclusion-exclusion but I wouldn't be surprised if it was possible. The $h_k$ version of the identity is, I think, a special case of the Polya enumeration theorem.