I've been working with John Collins to improve latexmk's ability to work with automake (actually, I've been talking, he's done all the work).
He's put up a snapshot at: http://www.phys.psu.edu/~collins/latexmk/trial/ together with a test project. Thoughts? Very sensibly, I think, John has modelled latexmk's handling of dependencies on the way the C compiler and makedepend work. The work is all on the latexmk side; there's no corresponding automake support; but hopefully the latexmk changes make it easier to support. I believe there is support for VPATH builds, but I've not yet had time to look at this myself, so I thought that I'd pass it on to the list anyway. John says: Notice that in addition to a -deps option, latexmk has acquired some other options. The relevant ones are -deps-out=filename, which sets the filename for the dependency output, and -recorder, which sets the use of the -recorder option on latex and pdflatex. The -recorder option is something I've planned for a while; it improves latexmk's detection of which files are read and written by latex and pdflatex. -- http://rrt.sc3d.org