me that this would not only have to be implemented in Perl
    which already doesn't look very inviting,

I have the impression that the development makeinfo can already do
proper Unicode sorting of the index terms, if desired.  Patrice?

    but also in TeX which (for me at least) skews any cost-benefit ratio :-).

:).  No index sorting has ever been implemented in texinfo.tex.  It's
done with a separate C program, texindex, which remains essentially in
its original state as of 1987 or so, sorting ASCII.  Life goes on ...

Best,
Karl