The easiest way to achieve this is to pipe your list of files through a sequence of commands:
locate your-search-term | xargs stat --printf '%.Y\t%n\n' | sort -n -r | cut -f 2-
The first line locates your files — you know this already. The second line stat
-s a file and prints the last modification time (epoch seconds) and the file path, for each located filename. The third line sorts the lines numerically descending. The last line cuts the modification time and the separator from each line, leaving the original path.