Permalink Manager codebase was optimized to avoid the performance issues. To reduce the number of SQL queries, the plugin saves all the custom permalinks in a single serialized array. The main reason for this is that the operations on arrays are generally quicker if they are made directly via PHP.
The plugin works perfectly fine with small and medium sized websites and WooCommerce stores. It means that you can use it to rewrite hundreds and even dozens of thousands of custom permalinks without any hassle.
However, there is one potential drawback of this approach. If you would like use it to rewrite more than 60.000-80.000 permalinks you might experience a slight slowdown. In such a situation, the first recommendation would be to simply exclude the content types that do not need to be filtered my plugin (eg. attachments).