How to recalculate Follow Path animation after curve length has been altered?
Semi Quick Overview

When your path has multiple temporal/spatial milestones that can move, create a path and constraint for each, create [influence] keyframes, for maintainability in the future.  Blender to the future.  The more milestones you have the more maintainability is an issue.

In the images above in the 3D view the green ball has two follow path constraints.  One path constraint to the yellow curve and one to the red curve.  Positive constraint [influence] means, influence = 1. The graph window shows that the constraint [influence] on a frame, is 1 for only one constraint at most and switches discretely to 0 in one frame.  The [influence] curve has four values [0,1,1,0].  When the [influence] is 0 the constraint has zero effect.  The [offset] curve has two values[0,1]. The constraints can independently be deleted or (enabled/disabled with the eye) and the other one will have a predictable affect.

In the 3D View are two Bezier curves, red and yellow which visually appear continuous by position and slope.  The two curves which were originally one and were [separated] to preserve slope/position continuity (piece wise continuous).  The green ball first follows the yellow curve and then the red curve. The movement is smooth across curves. Speed continuity is reasonable because the constraint influence curve has value 1 for a designed range of frames.  

Curves are different colors and have positive bevel for explanation purposes only. Curves need not be rendered.  The image on bottom is to emphasize the graph [influence] values as they transition.  

In this example I have repeated the location for one frame.  Change the end [offset] to a number such as ( 1 - (1/[number of frames in range])) if this suits your goals.

Method 1 Verbose Discussion of above


If you will be changing paths often this work will be to your advantage.
Consider two or more contiguous paths.   This will allow easier independent control of position and thus speed.  Create a longer path from pieces of shorter paths.  These paths will have influence on distinct ranges of frames/time and thus will ease the [Oh no! I have to change the path!] problem.
In the discussions below N1 and N2 are frame numbers such that 0 > N1 > N2 and N2 > N1 + 2.  We use the names path 1 and path 2.  FrameRange0110(f1, f2) means [influence] keyframes set on four frames. 0 > f1 and f2 > (f1 + 1), that is the range is two keyframes at least long for ease of discussion. Frame (f1-1) = 0.  Frame f1 = 1. Frame f2 = 1. Frame (f2 + 1) = 0. Four [influence] values [0,1,1,0] listed in increasing order of (frame or time). FrameRange0110(f1, f2) also means constraint [offset] values which are Frame f1 = 0 and Frame f2 = 1.  Two values indicating beginning and end of curve [0,1].  Every FrameRange0110(&lt;.>, &lt;.>) denotes 6 keyframes.
Independent Frame Ranges.  Lets also call two Frames ranges A = FrameRange0110(s1, e1) and B = FrameRange0110(s2, e2) Independent, if the positive [influence] values do not overlap in frame or time. Either (e1 &lt; s2)  or (e2 &lt; s1). The 0 [influence] of one range may exist with the positive [influence] of  another range, which should be the case for this particular example.
Action. For path constraint 1 with curve 1 create Range 1 = FrameRange0110(1, N1).
Action. For path constraint 2 with curve 2 create Range 2 = FrameRange0110(N1 + 1, N2)
Range 1 and Range 2 are now independent frame ranges and have convenient control.
This can be extended to many curves so long as the all path constraints are pairwise independent. Make small adjustments to suit your needs. Once you get independent control you might try some advanced mix of influence for interesting results.
To edit the range of influence for two adjacent curve you can select 4 adjacent points in two contiguous ranges in the Graph Window and move them in the X direction respecting the notion of Frame Range independence.


Advanced


In certain circumstances visual objects can control the Bezier curve itself.  
By using [influence] keyframes with two curves and no independence one can add circle wobble which is different than the curve noise modifier. The second curve could just be a circle or other closed curve with curve cycles modifier.  Curve placement is being added.


Beware


It is not clear that simple scaling of dopesheet frames will  produce acceptable/predictable results.  I have not seen documentation of how parametric distance is calculated in Blender. Complications are Bezier versus Path. Similar mathematical information is published in computer graphics books.  It might be difficult to determine which particular method Blender uses.  
Looking at source code may be more difficult than Method 1.


Method 2 (Superstitious)


Reflect on the likelyhood of further path changes.  If you believe no further changes are coming then just use the new curve and set new keyframes.  You have only doubled your work for this task.