As far as a straight speed search I can't think of anything faster than find. Its pretty lightweight as is. If the files you are scanning are spread across multiple disks you could run find's in parallel on each one assuming you aren't CPU bound.
With that said, depending on what you are trying to accomplish there could be mechanisms that you could implement to make this type of thing more efficient. Something like a memcache installation leveraging inotify/gamin could keep track of file system changes, or leveraging audit. I've never done anything like this on a file system with millions of files, so testing would be needed.
What is your use case? If this is just a one time investigation, writing the mod dates to a file would probably make successive searches a bit faster.
