Can the off-diagonal elements of Fisher information matrix be negative? The concept of Fisher information is new to me and as I understand the diagonal elements of the Fisher information matrix (FIM) are proportional to mean square error (to be precise the inverse of FIM). What is the interpretation of the off-diagonal elements of FIM and can these be negative?

There is a link between Fisher information matrices and covariance matrices, see Demonstration and Interpretation between a Fisher matrix and its dual space which is covariance matrix  for details.  So asymptotically Fisher information can be interpreted as an inverse covariance matrix, that is, a precision matrix.  For derails see How to interpret an inverse covariance or precision matrix?  and especially Why does inversion of a covariance matrix yield partial correlations between random variables?.
Partial correlations can certainly be negative.
