It is grammatically correct, but unusual: most people would add a comma before as to make it easier to read.
He exerted total supremacy over his enemy, as when he defeated the whole army himself a few years ago.
It can be made a bit more readable by adding he did:
He exerted total supremacy over his enemy, as he did when he defeated the whole army himself a few years ago.
The meaning of as in this context is defined in the Oxford Dictionary, meaning 2 as: Used to indicate by comparison the way that something happens or is done.. A more common example of this usage would be:
He went to work by bus, as usual
as has a lot of possible meanings so its usage can be confusing. You could use like, but as you mentioned it does sound rather informal. Alternative ways of saying the same thing formally in this context would be such as or for example.