show/hide this revision's text 3 added 139 characters in body; [made Community Wiki]

EDIT: My answer is wrong, though not for the reason given by the commenter; I read the absolute values as being inside the summation.

This is false. Consider the matrix $$\begin{pmatrix} \epsilon/2 & 0 \\ 1-\epsilon/2 & 1 \end{pmatrix}.$$

Letting $f$ be the identity and $g$ the only other permutation, the sum is on the order of $\epsilon$, not $\epsilon^2$. Furthermore, rearranging sums easily gives $\epsilon$ as an upper bound in the general case, assuming the entries are all positive.
show/hide this revision's text 2 fixed typo; deleted 34 characters in body

This is false. Consider the matrix $$\begin{pmatrix} \epsilon/2 & 0 \\ 1-\epsilon/2 & 1 \end{pmatrix}.$$

Letting $f$ be the identity and $g$ the only other permutation, the sum is on the order of $\epsilon$, not $\epsilon^2$. Furthermore, rearranging sums and using the triangle inequality easily gives $\epsilon$ as an upper bound in the general case, assuming the entries are all positive.
show/hide this revision's text 1

This is false. Consider the matrix $$\begin{pmatrix} \epsilon/2 & 0 \\ 1-\epsilon/2 & 1 \end{pmatrix}.$$

Letting $f$ be the identity and $g$ the only other permutation, the sum is on the order of $\epsilon$, not $\epsilon^2$. Furthermore, rearranging sums and using the triangle inequality easily gives $\epsilon$ as an upper bound in the general case.