Rather he believes them.

I would read it that way, yes. It is subtle, though. The phrase more accurately means "He believes they exist". To mean something like "He believes what they say", the proper phrase would be:

saverye quetielta "(lit.) He believes their words"

Another example.

The best translation of saven Eldar would be "I believe in Elves", that is that Elves exist. To translate "I believe the Elves", that is that what they say is true, the construct is as above:

saven i Eldaron quetier "I believe in the words (or sayings) of the Elves"

Hm. I wish to add no-one noticed that it is savéset or at least savesset that would mean that. There is no inflection rye.

Doh! +Александр Запрягаев is right. I'm embarrassed I missed that.

The connecting vowel is i in the aorist.

Indeed. So my choice would be savis te or possibly savisset for 'he believes they exist'.

+Björn Fromén I think it's probable that the unquoted word 'to trust (a person)' is actually vore BOR. This way vórima, voronda are perfectly understandable. The Etym entry does not exactly contradict this, it is just more compact; otherwise vórima (with a long vowel) becomes a peculiar example of a verbal derivation from something totally non-verbal. And vórima as 'trustworthy' is a super-straightforward interpretation.

The sentence in question is Túro nyanyarra tenna savisset. Túro keeps telling tales until he believes them. Correct?

+James Coish nyanyarra? I would say nanyarra (only the core component repeats). And savíset (or rather save te, as the subject's here).

I used tyatyamba as a guide for nyanyarra.

+James Coish How about Túro nanyarra tenna savis i nyarnaryar naiti ('T. keeps telling until he believes that his tales [are] true')?

Yes, that may have a more clear meaning.

would "keeps telling himself" be *nyanyarraxe since there is a subject?

+James Coish​ in my mind, the -xe suffix is for actions that are inherently reflexive, like washes himself, combed her (own) hair, - in this regard akin to the Russian suffix -sya or Polish enclitic sie. For other situations like yours I would use immo and its inflected variants, i.e. nyanyarra insen.

But I may be sorely mistaken and Tolkien may have intended both constructs to have the same meaning (immo is later than -xe)

My guess is that -xe is possible only when the reflexive is the direct object of the verb. In "tell himself sth" it's the indirect object (= "tell sth to himself") and thus would require a dative or allative of immo/inse as Tamas suggests.