For the record, I can reproduce the issue with this minimal test file:

mdk@windhowl$ ls -lah
total 108K
drwxr-xr-x  2 mdk  mdk  4.0K Oct  2 21:15 .
drwxrwxrwt 18 root root  96K Oct  2 21:15 ..
-rw-r--r--  1 mdk  mdk   196 Oct  2 21:13 faq.tex

mdk@windhowl$ cat faq.tex 
\documentclass[a4,10pt,french]{report}

\usepackage[utf8x]{inputenc}
\usepackage[T1,T2A]{fontenc}
\usepackage{babel}

\begin{document}
\tableofcontents
\chapter{FAQ sur Python éh}
\end{document}

mdk@windhowl$ latexmk faq 2>&1 | tail -n 15
(/usr/share/texlive/texmf-dist/tex/latex/ucs/data/uni-0.def) [2] (./faq.aux) )
Output written on faq.dvi (2 pages, 608 bytes).
Transcript written on faq.log.
Latexmk: Log file says output to 'faq.dvi'
Rule 'latex': File changes, etc:
   Changed files, or newly in use since previous run(s):
      'faq.aux'
      'faq.toc'
Latexmk: Maximum runs of latex reached without getting stable files
Latexmk: Did not finish processing file 'faq':
   'latex' needed too many passes
Latexmk: Use the -f option to force complete processing,
 unless error was exceeding maximum runs of latex/pdflatex.
Latexmk: applying rule 'latex'...
Latexmk: All targets (faq.dvi) are up-to-date


Also, according to matrixise, it works with xelatex.