How to call latexmk in emacs, and jump to next-error

I would like to use latexmk to compile my LaTeX documents in Emacs. Especially I need the Emacs functionality next-error, which is typically called with C-x `, and jumps to the next LaTeX error in the document.

I would like to call latexmk either using C-x compile or the AUCTeX C-c C-c.

First, I set latexmk to use

$pdflatex = 'pdflatex -interaction=nonstopmode';

Option 1: C-x compile

I press C-x compile and type latexmk -pdf foo, which runs pdflatex. But next-error will not jump to the errors, even if the *compilation* buffer contains errors:

! Paragraph ended before \author was complete.
<to be read again> 
                   \par 
l.48 
[...]
Compilation exited abnormally with code 12 

How can I automatically jump to this error in line 48?

Note that this question of parsing the latex output has nothing to do with latexmk directly. The same problem occurs when I just do C-x compile pdflatex -interaction=nonstopmode foo.

Option 2: AUCTeX

How can I set AUCTeX to call latexmk -pdf instead of pdflatex on my .tex file? Of course, I want next-error to work here too.

UPDATE: I started a bounty because if this worked it would be a great tool for many people. I consider the question answered if a solution is given that lets me easily compile my LaTeX document using latexmk in Emacs and jump to the errors using next-error (of course, the errors might be in included .tex files, not necessarily in the master file or the current buffer).

UPDATE: Thanks to Ivan (and Chris) for making AUCTeX+Latexmk work. In the meantime, I found that using Rubber to compile LaTeX is also an excellent choice. It will display error messages in the format used by gcc and other compilers, so it naturally works with Emacs C-x compile, e.g. C-x compile rubber --pdf foo, and the error messages are parsed correctly.

Sorry I don't have the ability to comment, or I would just add this as a comment. Chris Conway's answer works, except that it should use TeX-run-TeX instead of TeX-run-command so that AucTeX knows to process the error messages.

(add-hook 'LaTeX-mode-hook (lambda ()
  (push 
    '("Latexmk" "latexmk -pdf %s" TeX-run-TeX nil t
      :help "Run Latexmk on file")
    TeX-command-list)))

It might also be wise to add something like

'("%(-PDF)"
  (lambda ()
    (if (and (not TeX-Omega-mode)
             (or TeX-PDF-mode TeX-DVI-via-PDFTeX))
        "-pdf" "")))

to TeX-expand-list and use "latexmk %(-PDF) %s" so that it will work in both pdf and dvi mode. Personally, I find it easier to use customize especially when you are experimenting.