What are sentences like "the longer X, the more Y" called and can they be used in formal written English?

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.

I think that what you're looking for is covered by the concept of parallelism. There are a number of rhetorical devices that use parallel structures to provide emphasis to a relationship; Anaphora is one that looks promising as a formal term.

It's my opinion that it's very much valid to use in formal english, especially as it has a greek name attached and is a formal rhetorical structure ;-P

It is called comparative correlative or conditional comparative:

In grammar, a comparative correlative is a minor sentence pattern containing two corresponding phrases or clauses, each one headed by the and expressing a comparative: the X-er . . . the X-er or the X-er . . . the Y-er.

The comparative correlative is also known as the correlative construction, the conditional comparative, or the "the . . . the" construction.

Grammatically, the comparative correlative is a type of paired construction; rhetorically, the comparative correlative is often (but not always) a type of parison.

http://grammar.about.com/od/c/g/Comparative-Correlatives.htm

I don't know a special name, but I know where I find it in grammars: in the chapter Adjectives and there under comparative forms. The better, the more expensive or in full form The better something is the more expensive it is - such structures are used in spoken and written language. I think mathematicians call such a relation between two values proportion or direct proportion and one might use the term proportionality. But grammars normally don't use a special name. You find it in the box "comparison".