How does the charging curve of a deep-cycle lead-acid battery change as it degrades?
The discharge curve does not scale or change as capacity is lost.  You cannot use terminal voltage to estimate runtime on a given battery.

To be clear, there are two intertwined but very different concepts here: state of charge, and remaining capacity.  

State of charge is simply how charged up the battery is.  This is always in a percentage of the battery's capacity.  This is what you can estimate by measuring the terminal voltage.  And I do mean estimate, as open circuit voltage is fairly inaccurate unless the battery has been allowed to rest (neither loaded nor charged) for 4-24 hours, with accuracy improving the longer you wait.  Any recent charging or loading will distort the terminal voltage and introduce significant error and throw off the true state-of-charge.  You can get a rough estimate by just measuring the open circuit voltage when open circuit but 'unrested', but it would not be accurate enough for anything like a runtime, unless the runtime is fairly vague.  

The really important subtly here however is that measuring state of charge tells you nothing about the battery's actual capacity.  A battery that is at a 100% state of charge will have (generally) the same terminal voltage when it is at this 100% state of charge regardless of the actual capacity.  100% means it has been charged to its maximum capacity, which varies with age, use, abuse, cycle count, etc.  

You can charge a battery with 50% of its rated capacity left (in other words, well past when it should have been taken out of service, at least for deep cycle lead-acid batteries), and when it is fully charged, its state of charge will be 100%.  100% of its present capacity, which is 50%.  The terminal voltage will be the same as a totally new, 100% of rated capacity battery that is also at 100% state of charge.  State of charge tells you nothing about how much energy is actually stored in the battery.  All it tells you is how empty or full the battery is, without telling you the size of the tank.  

Remaining capacity is, well, the actual 'size' of the battery, or how much energy it can store.  Batteries will have a rated capacity, which is the amount of energy the should store when new.  As they degrade, the amount of energy they can store begins to shrink.  This has no effect on the terminal voltage, except maybe when the battery is severely degraded and or damaged, then certain wear mechanisms can distort the curve in unexpected ways, but any battery behaving like this should be removed from service anyway.  

The terminal voltage is determined by the battery's chemistry and specific construction, it does not vary with capacity.  Remember, a battery's capacity is just a rating - a number that the manufacturer measured and expects, but that's all.  A battery has no idea what capacity it is 'supposed' to be, it is only the capacity that it is.  Put another way, you can measure the capacity of a battery by discharging it to a cutoff voltage, but this is all you can measure.  There is no way to determine what the 'intended' capacity of that battery is.  It might be at 120% of the rated capacity, or 60%, but the only way to know is if someone has told you what the capacity should be.  By itself, no battery 'should' be a capacity, a battery is always simply the capacity it currently is.   

So, simply but, the curve, in terms of terminal voltage, will not change at all as the battery's capacity degrades.  If it did change, then we would need different battery chargers for different sizes of batteries of the same chemistry, as a 20Ah SLA would have a different curve compared to a 7Ah SLA.  But of course, we divide chargers by the chemistry of the battery they are to charge, and capacity is irrelevant.  

For your application, which is giving the user an estimated run time (I'm guessing you know the load ahead of time?), cannot be done while the battery is disconnected from the load in question.  You could attempt to use a coulomb counter to estimate how much energy is stored in the battery during the bulk charge phase, but this will become increasingly inaccurate as the battery wears out.  This technique works well for things like Lithium Ion batteries, but it is less useful for lead acid chemistries.  Lead acid's ESR and other sources of dissipative losses will increase with significant hysteresis or 'memory' depending how the battery has been used so far, nothing close to linear or predictable.  Beyond this, lead-acid charging efficiency is relatively poor and highly variable with temperature.  Energy used to charge the battery is always going to be fairly different from the energy actually stored in it, in the case of lead-acid batteries anyway.

And of course, this cannot account for capacity lost due to aging, which is the primary loss mechanism I would expect for a UPS.  It's no good.  

You should not try to give a runtime estimate ahead of time.  You cannot actually estimate this with any reliability, and it would serve to simply give the end user a false sense of security, while hiding the true state of the battery.  

The only feasible way to estimate run time in this application is dV/dt.  In other words, once the battery is actively loaded, you keep track of how quickly the terminal voltage is falling over time.  This allows you to leverage the fact that regardless of capacity, the battery's terminal voltage vs. state of charge should remain more or less the same (assuming the battery isn't too old or damaged anyway).  So you can measure how rapidly it is losing state of charge, and estimate the remaining run time that way.  This is why any decent UPS with some sort of 'test' function will not only disconnect the battery from power, but temporarily run the load connected to it entirely from the battery, usually for 60 seconds or more, as this is the only means of getting a good estimate.  If you did this automatically and periodically, then you might be able to provide a run time estimate ahead of time that is reliable enough to be useful/responsible.   However, the longer you wait between tests, the less accurate this number will be, but the more frequently you perform this test, the quicker the battery will wear out, so it is up to you to decide what is most important, and find a balance for your application.  

Batteries are subtly complex, cruelly fickle, and messy in a way that only something fundamentally electrochemical rather than electronic can be. In other words, batteries are hard (for us engineers) to deal with.  Good luck!