What is the difference in meaning between the two?
I saw him as lately as the last Monday.
I saw him as lately as Monday.
Meanwhile, would you possibly show me what "as lately as" means?
Like @TRomano said, we would say "as late as" meaning the very last moment that this has happened. We would not use "as lately as" because lately is a adverb - which means it would need a verb to describe. To use lately you'd want to say:
I haven't seen him lately
However, we would use "as late as" in this case:
I saw him as late as (last) Monday.
This means that the very last time you saw him was (last) Monday and no later.
Teachers will sometimes use it for the future when assigning homework:
You can turn it into me as late as Monday
Meaning your deadline is Monday, and no later. (They will not accept it on Tuesday).