Something really quick I noticed in the RAM viewer: there's this byte at $06b5 (aka $c6b5) that goes up every step or so... It seems if you keep it really low (like 1), random encounters appear much more rarely. Maybe the game uses this number as a % of probability (ie, if there's a 20 there, a battle can come up 20 out 100 times). Also, if set to 0, it seems there are no random battles at all.
Well, you're right that it's a step counter, good job. It increments every step, unless it reaches $10, in which case it stays at that. After it checks this step counter it calls a routine which I assume is an RNG routine, but I'm not familiar enough with such things to know. Suffice to say that freezing it at $01 means that encounters are very rare, and freezing it at $10 means encounters occur very quickly.
So, what is obviously happening is the game sees how many steps you've taken and makes a 'dice roll' to see if you have an encounter or not. To use a board game analogy, it's a bit like rolling 2D6 and having to get 13, but adding 1 to your roll for every step you've taken. Thus, zero steps means no encounter, and the more steps you make, the more likely it becomes. At least, that's how it seems to me.
I'll make a routine to only increment every other step, and see what happens.
EDIT: and I'm done.
Just patch the ROM with this and it adds a little routine, which I shall now explain.s346165667.websitehome.co.uk/psyktrans/metalwalker-encounter.ips
Quite simply, the patch breaks out of the regular program to check a (hopefully) unused RAM address, $C6FF, to see if it's zero. If it is, it increments it and loads the step counter as normal. If it's not zero, it decrements it (bringing it back to zero) and decrements the step counter. Then when the step counter is incremented as normal, it basically means it doesn't change. Therefore, your step count only increases on each alternate step. As far as I can see there are no problems with this, and I assume the encounter rate appears much less - but you'll have to test that yourself.
Hat tip to KingMike for suggesting the 'spare RAM address' idea in his DTE tutorial that taught me a lot about assembly.