The gaining of the levels is actually quite a simple algorithm, but like anything in assembly, it's annoying to decode. I found the assembly code which deals with HP, but I just don't want to trace it right now for 2 reasons: 1 - I am doing something else and I don't have time for it right now, and 2 - The algorithm is so simple, you can figure it out by mere observation, (and looking at a little bit of code too) so here it is:

Every unit, as you said, starts with 100 HP:

00:B4AB:A9 64 LDA #$64

00:B4AD:85 10 STA $0010

This value is hard-coded for everyone right here. You can use the following Game Genie code to start with 200 HP instead of 100 as an example:

// Start with 200 HP instead of 100:

// B4AC ? 64 : C8 = EKXUGGGV

Note that this will be for executable code, so this determines your Max HP when you start the game, and when you get a level-up, so its not like you can put in the code, disable it, and then continue from 200 HP after a level-up. The 100 value is hard-coded into the algorithm.

Now, you will notice that, instead of going from 100 to 114 HP on the first level up for Guan Yu, you will go from 200 to 228. Everything is doubled, including the level-up amount (from +14 to +28)

The algorithm simply adds a certain percentage of your current HP to your total for each level gained. The formula is the following for EVERYONE:

Current Max HP = 100 * ( ( 256 + DX ) / 256 ) ^ ( level - 1 )

The value of DX is different for each General (or potentially different, some of them can re-use the same value. :p

For Guan Yu, DX = 0x24 == 36.

For Zhang Fei, DX = 0x26 == 38, which gives us:

Level --- Soldiers

1 = 100

2 = 114.84375

3 = 131.890869140625

4 = 151.4684200286865234375

5 = 173.95201362669467926025390625

50 = 88157.829677227159636497911258936

NOTE that I used a calculator to generate this simple, sample table, and this is WRONG. A calculator will work with floating-point values, but the game works with discrete numbers. There is no exponential opcode in NES assembly. You have to multiply the value n times, so you should get:

1 = 100

2 = 114

3 = 130

4 = 149

5 = 171

...

Now, how does the game determine what DX is? Well, it uses the values you posted to look into an array:

00:B4D6:B9 0B B5 LDA $B50B,Y @ $B51F = #$26

$B50B == 0x3B51B

where Y == the value you posted that is less than 0x80. (Zhang Fei == 0x14, Guan Yu == 0x0A)