I don't know if there's a name for such sentences themselves, but they are surely appropriate in formal English:
Bible search results for "the more". Here are only some of the various possible syntactical structures:
- But the more they were oppressed, the more they multiplied and spread; so the Egyptians came to dread the Israelites. (Exodus 1:12)
- For with much wisdom comes much sorrow; the more knowledge, the more grief. (Ecclesiastes 1:18)
- The more priests there were, the more they sinned against me; they exchanged their glorious God for something disgraceful. (Hosea 4:7)
British National Corpus search results for "the more". Again, just a couple examples:
- The higher the Péclet number, the more contorted the pattern must become before this happens.
- The more correct the early stages of training, the less chance there is of things going wrong.
- [T]he more I worked on it the more it began to evolve into another kind of idea and the more removed it became from my initial study which had so much freedom and energy, so I stopped.
- Crudely, the more effort involved in processing a metaphor, the "better", or the more poetic, the metaphor is supposed to be.
Wiktionary says:
Adverb
1. With a comparative or more and a verb phrase, establishes a parallel with one or more other such comparatives.
- The hotter, the better.
- The more I think about it, the weaker it looks.
- The more money donated, the more books purchased and the more happy children.
- It looks weaker and weaker, the more I think about it.
2. With a comparative, and often with for it, indicates a result more like said comparative. This can be negated with none.
- It was a difficult time, but I’m the wiser for it.
- It was a difficult time, and I’m none the wiser for it.
- I'm much the wiser for having had a difficult time like that.
The corresponding Merriam-Webster entry reads as follows:
1 : than before : than otherwise —used before a comparative <none the wiser for attending>
2 a : to what extent <the sooner the better>
b : to that extent <the sooner the better>
Do note that — as the third Wiktionary example and the last two of the BNC examples quoted above demonstrate — the chain is not limited to just two items. In fact, there is no theoretical limit, only a practical one that depends entirely on context.
Also (and this is addressed by both Merriam-Webster and Wiktionary, but I think I should expressly state it here), this the is etymologically not the same as the article the. The article comes from Old English þē, a variant of sē, while the adverb comes from Old English þȳ, the instrumental case of sē and þæt. If we look at related languages, e.g. German where the article would be der, the construction "the more, the better" is still formed with a different word even today: "je mehr, je besser" (or "je mehr, desto besser"). Follow the Wiktionary link for more infos.
This construction is not limited to Germanic languages, either. Russian has "чем... тем...". French has "plus... plus...". A fellow poster provides additional information in his answer to a related question. He also simply and elegantly calls this construction the "parallel comparative", which is not a term I've used before, but one that is conveniently self-explanatory.