Okay, I think I have it figured out - it was much simpler than I imagined. Not pretty, but here's the relevant code to update legend labels:
x = lyr.symbology.classBreakLabels
a = "0 - 50%: " + x[0]
b = "50 - 75%: " + x[1]
c = "75 - 90%: " + x[2]
d = "90 - 95%: " + x[3]
e = "95 - 98%: " + x[4]
f = "98 - 100%: " + x[5]
lyr.symbology.classBreakLabels = [a,b,c,d,e,f]
The output looks something like this in the legend:
0 - 50%: 0 - 10
50 - 75%: 11 - 20
75 - 90%: 21 - 30
etc...
It exports to PDF correctly, which is exactly what I need! Hope this can help someone else.
