The key was in using the magical -execdir option to find rather than just -exec.
Info on dirname and basename: https://stackoverflow.com/questions/2536046/extract-directory-path-and-filename
This StackExchange answer provided the key information which is that dirname wasn't going to help me because it is evaluated before find! Also the backwards quotes for using the evaluation of a command inside a command line. https://unix.stackexchange.com/questions/339880/cp-not-evaluating-dirname-properly-in-find-operation?rq=1
Here are some harder ways to do it with xargs: https://stackoverflow.com/questions/17368872/how-to-move-or-copy-files-listed-by-find-command-in-unix
My final command line:
find . -name "Prefix*.txt" -execdir cp -p `basename {}` newfilename.txt \;