This is a very similar problem to the ramp up / ramp down for stepping motors. Basically instead of making the time to the next change a fixed interval make it one you calculate from a fixed value plus (or minus) the number of steps you have made in the fade, times a constant.
Can you hack that or do you want more of a pointer?