It is probably best to rename the photos before you export them. Otherwise, your clients will be referencing a number that you probably won't have associated with the files in your catalog. In the library module, simply highlight all the images and then press F2. This will bring up the rename menu and you can choose your naming format. But if you really want to rename during export there is a renaming option on the export dialog where you can assign a custom name plus a sequence number. That way your photos will be numbered sections with the name of the client plus a number.
Might I suggest to rename so that the catalog Filename is incorporated in the new 'Exported' Filename.
If you want to preserve your original filenames in the catalog, use this re-name in the Export dialog only.
In the filename editor you could use something like- (saved as a preset)
You could choose this Preset with some Custom text like-
So if you rename 12345.tif you will get NEW JOB_20160329_0001_12345.tif
Sorry got carried away with last answer-
In simpler form use something like- Sequence_Filename Number Suffix
So an image like _ABC0987.nef would become 0001_0987.nef and 0002_0988.nef, etc.
Ask your client to give you the full filename. The suffix will indicate the original file.
(Hopefully you only need to search in one folder and do not have heaps of images named the same which would cause problems!)