My plugin has several custom post types and the main one I want to make its permalink slug changeable. I would prefer to keep things clean and add that option in WordPress’ Permalink admin screen, below category base and tag base.
How can I hook into that though, I can’t find anything but I know it’s possible (Woo does it, amongst others)?

To hook your custom plugin settings into the Permalink settings, use the following:
add_action('admin_init', 'wpse_237141_custom_permalink_section');
function wpse_237141_custom_permalink_section() {
add_settings_section(
'your_custom_id', // ID
'Your Plugin Settings', // Section title
'your_callback', // Callback for your function
'permalink' // Location (Settings > Permalinks)
);
}
You’ll need to fill in the blanks to display your own custom functions, but this will now display your settings in the Permalinks.