I think $f$, $g$ exists for all $n$. First, we can easily see that if $f$, $g$ exists for $n$, they also exist for $n-1$. (Just let $x_{n}=0$ and we get $f$, $g$ with $n-1$ variables) Now we construct $f$ for odd $n$. \[f(x_1,x_2, \cdots, x_n)=\prod_{\emptyset\neq S\subset \left[n\right], \left|S\right|\leq (n-1)/2 } \left(\sum_{i\in S^{c}}x_{i}-\sum_{i\in S}x_{i} \right)\]Then, we can see that when you plug any $-x_{i}$ instead of $x_{i}$ in $f\times \sum_{i=1}^{n}x_{i}$, the polynomial does not change. (The degree of $f\times \sum_{i=1}^{n}x_{i}$ is $2^{n-1}$) Thus, there exists $g$ such that $f(x_1,x_2, \cdots, x_n)\times \sum_{i=1}^{n}x_{i}=g(x_{1}^2,x_{2}^2, \cdots, x_{n}^2)$