Modifying the URL structure always consists of two parts: one two modify the URLs you generate with your code, and one to handle the incoming URLs of the new structure. I will focus on the second, and maybe least understood, part.
The incoming URLs are matched to different rewrite rules, which are regular expressions that can match the URL. These expressions can have capture groups which capture a part of the URL to send it to different query variables, which are (for example) used to construct the database query. If you create a custom post type slideshow, one of the rewrite rules will look like this:
slideshow/([^/]+)(/[0-9]+)?/?$ => index.php?slideshow=$matches[1]&page=$matches[2]
This means we match a URL that starts with slideshow/, then anything up that is not /, and optionally (the ?) a / and any number of digits. The first match is sent to the slideshow query variable, the second match to the page variable. For example, slideshow/nature/2 will set slideshow to nature and page to 2. I wrote a plugin that might be helpful in understanding and debugging your current rules.
You would like to match a structure like slideshow/nature/slide-2-canyon/. The regex for this looks like:
slideshow/ // Start with 'slideshow/'
([^/]+) // Then anything that is not "https://wordpress.stackexchange.com/"
(/slide- // Then 'slide-'
([0-9]+) // A page number
(-([^/]+))? // Slide title: '-' and anything that is not "https://wordpress.stackexchange.com/". Optional so you don't have to add it
)?/?$ // Which could be followed by a "https://wordpress.stackexchange.com/"
We want to capture the slideshow name and the page number. You count the opening ‘(‘ to get the match indexes, so our full rewrite rule looks like this:
slideshow/([^/]+)(/slide-([0-9]+)(-([^/]+))?)?/?$ => index.php?slideshow=$matches[1]&page=$matches[3]
Now, we just need to add this to the rewrite rules. Make sure you put it at the top, as a similar rule is used to match for attachments of a post, and your custom rule would never be hit if it is at the bottom of the list.
add_rewrite_rule(
'slideshow/([^/]+)(/slide-([0-9]+)(-([^/]+))?)?/?$',
'index.php?slideshow=$matches[1]&page=$matches[3]',
'top'
);
It is enough to only call this line once, and then flush_rewrite_rules(). Or, if you don’t want to mess with plugin activation hooks, call the add_rewrite_rule() on every init, but then load the “Permalink” settings page to flush the rules. As long as you don’t flush the rules on every page load, because it is an expensive calculation.
The only thing left for you is generating page links of the new format. wp_link_pages() seems to offer no filters to modify its output, so I would study how it works and duplicate it with your page format (it’s not hard, and you only need half of the function if you choose only one output format).