The following command will replace match with replace for all files in the cwd, and create a soft link to the new file name using the old file name.
$ find . -name '*.mkv' -type f -exec bash -c 'mv "$1" "${1/match/replace.}" && ln -s "${1/match/replace.}" "$1"' -- {} \;
So:
ls -l
total 27477872
-rw-r--r--. 1 george media_ 3517838477 Jan 9 20:04 match04e01.mkv
-rw-r--r--. 1 george media_ 3518691716 Jan 9 20:06 match04e02.mkv
-rw-r--r--. 1 george media_ 3517770051 Jan 9 20:06 match04e03.mkv
-rw-r--r--. 1 george media_ 3518279808 Jan 9 19:49 match04e04.mkv
-rw-r--r--. 1 george media_ 3518602594 Jan 9 19:48 match04e05.mkv
-rw-r--r--. 1 george media_ 3509398082 Jan 9 20:08 match04e06.mkv
-rw-r--r--. 1 george media_ 3518737024 Jan 9 19:50 match04e07.mkv
-rw-r--r--. 1 george media_ 3518008059 Jan 9 19:48 match04e08.mkv
Would become:
ls -l
total 27477904
lrwxrwxrwx. 1 root root 30 Jan 10 23:27 match04e01.mkv -> ./replace.s04e01.mkv
lrwxrwxrwx. 1 root root 30 Jan 10 23:27 match04e02.mkv -> ./replace.s04e02.mkv
lrwxrwxrwx. 1 root root 30 Jan 10 23:27 match04e03.mkv -> ./replace.s04e03.mkv
lrwxrwxrwx. 1 root root 30 Jan 10 23:27 match04e04.mkv -> ./replace.s04e04.mkv
lrwxrwxrwx. 1 root root 30 Jan 10 23:27 match04e05.mkv -> ./replace.s04e05.mkv
lrwxrwxrwx. 1 root root 30 Jan 10 23:27 match04e06.mkv -> ./replace.s04e06.mkv
lrwxrwxrwx. 1 root root 30 Jan 10 23:27 match04e07.mkv -> ./replace.s04e07.mkv
lrwxrwxrwx. 1 root root 30 Jan 10 23:27 match04e08.mkv -> ./replace.s04e08.mkv
-rw-r--r--. 1 george media_ 3517838477 Jan 9 20:04 replace.s04e01.mkv
-rw-r--r--. 1 george media_ 3518691716 Jan 9 20:06 replace.s04e02.mkv
-rw-r--r--. 1 george media_ 3517770051 Jan 9 20:06 replace.s04e03.mkv
-rw-r--r--. 1 george media_ 3518279808 Jan 9 19:49 replace.s04e04.mkv
-rw-r--r--. 1 george media_ 3518602594 Jan 9 19:48 replace.s04e05.mkv
-rw-r--r--. 1 george media_ 3509398082 Jan 9 20:08 replace.s04e06.mkv
-rw-r--r--. 1 george media_ 3518737024 Jan 9 19:50 replace.s04e07.mkv
-rw-r--r--. 1 george media_ 3518008059 Jan 9 19:48 replace.s04e08.mkv