What additional pathfinding?
Imagine a 'maze walls' entrance, like some people use...
....#########....
....#+^+#+^+#....
....#+#+#+#+#....
....#+#+#+#+#....
->..++=+++=++..->
....#########....
That's a walled 'switchback' with some bridges for a short path that can be pulled up and some traps on the switchbacked routes.
Simple pathing would be straight through, with the bridges down, but if the bridges were pulled
up, then...
....#########....
....#+^+#+^+#....
....#+#+#+#+#....
....#+#+#+#+#....
->..++ +++ ++..->
....#########....
A current sieging force can only recalculate a path around the bends (and across the traps, which might make some hesitate). But an army with climbers could ideally just clamber over the walls adjacent to where the bridges were pulled up (or on top certain walls, wander around up there and then clamber down at the other side, if that's less of a movement penalty). And a sieging force with at least two 'bridging' items in their possession (another 'improved enemy AI/ability' option discussed in the past) could also just lay their own bridging materials across those gaps for everyone to wander through as before, if done wisely, and not used to bridge random pools that never really needed bridging in the first place.
When you get climbers/etc (whether restricted to clim-capable invaders, universal to those with the ability or somewhere in-between) you basically need to re-vamp the pathfinding algorithm to allow those that
can climb to generate climb-worthy paths (which in one implementation may mean duplicating the current non-climbing pathfinding information and then expanding it
greatly with all the places they can now reach that they couldn't before, as well as 'simplifying' that version of the pathing algorithm with quicker routes for which climbing is a necessity).
You can see the difference right now, with flying enemies. Flying enemies can route around non-walkable barriers by accident (random walking(/flying))
or by finding a walkable route (which may be twisty, liek the above) and using that as 'permission' to just fly over obstacles/gaps that are suddenly presented in their paths. If there
isn't a walkable route, then flyers (with access to just the basic walkable-route pathfinding data) only 'randomly' wander into areas sealed off in a ground-only fashion (but, once there, will run rampage). Or at least that's how hit
has been, but may have changed. Amphibious(/'magmaphibious') creatures probably are affected the same, with the appropriate non-obstacles.
In short, non-universal climbing is probably going to mean a performance hit.
(A shorter reply is: If all units did their own, and only their own, pathing calculations from scratch, then it would probably be not much more intensive. May even be less, as climbers reach their destinations sooner. But it's already optimised to some extent (to save some amount of duplication) and now you need now to double-(or triple-, or quadruple-)up the shared data to take account of those-that-can-climb and those-that-can-fly and those-that-can-swim and those-that-can-climb-
and-swim and... etc, on top of the basic one for those-that-can-only-walk...)
If I'm misremembering anything, apologies, but search for "Advanced Pathfinding Algorithm", or something in the forum (DF Suggestions, especially). You'll find several threads around with pathfinding as a subject, within which a number have discussions of dealing with creatures that can fly/climb/jump/bridge/tunnel (or any combination of these) on top of the normal pathing.