To debug performance problems, one approach is to use the built-in profiler:

    M-x profiler-start RET RET
    <reproduce the slowdown, ideally for a good 10s or so>
    M-x profiler-report RET

Then browse the report (`C-u RET` is an important command there) to see where all that time is spent.

Seeing your profiler report, you'll probably want to file a bug report with the markdown-mode maintainer to see how to change the code of `markdown-fontify-inline-links` to try and make it faster.