I've written scripts like this a few times, unfortunately not really ready to share here. The basic idea I've used is to build a list of files, e.g. using File::Find, storing the data I want to compare (be it filenames or checksums) in two hashes, one for each directory. For example, I might make the keys the MD5 sums and the values an arrayref of filenames, and then I'd basically do union and difference operations on the keysets. See e.g. "How do I compute the difference of two arrays? How do I compute the intersection of two arrays?" in perlfaq4 or my node here.

Minor edits for clarification.