They're both so unusual that old-fashioned doesn't really seem to apply. I like
Clemency - it's got a sweet sound and a nice meaning. (I like
Clement too, but I seem to be in a small minority there). Not so sure about
Clelia - the two 'l's look awkward to me somehow, but I think I could warm up to it.