You haven’t provided the details of your solution. So I commented on the provided code samples. Your solution should work for curved splines.
However, dividing the whole segment upfront into n straight pieces seems unnecessary, as that gives you linear complexity where logarithmic is possible. To explain: if your segment has 10 m and you want 1 m pieces for your approximation - you divide it into 10 pieces. But if you want to double the precision of your approximation by using 0.5 m piece, you need to divide into 20 pieces. Twice the amount of calculations/spline-sampling seemingly.
Binary search achieves the same, also diving the segment into straight pieces. But doubling the precision requires only one more iteration, thus logarithmic complexity. That is especially important for long splines with long segments.
There is a problem I found however - you can’t use a strict binary search - dividing a segment into halves each time. You have to divide with some extra margin - to account for the curvature of the segment. Otherwise the searched position may end up just next to your division point, but on the wrong side. And then you are running other iterations on the wrong piece of the segment. Adding something like 15-30% of margin (inflating the half you want to keep processing) solves the problem for most splines. And this really requires maybe an extra one or two iterations, so the performance is still great and complexity stays logarithmic.
There is also another source of slow down when sampling splines - finding the segment-idx to further analyze (FindInputKeyClosestToWorldLocation). UE does that using a linear search from the beginning of the spline. I also advise to replace that with binary search where possible (for slightly curved splines).