SHA-1 on a 90MHz Pentium cpu from the same year the Tamagotchi was released takes 837 cycles to complete, assume it would take 8x on a 6502 because of the difference in instruction width and instructions per cycle (I could be way off, so I will use 10X as a baseline here).
8370 cycles at 1MHz is just under 100th of a second. Even if it was several times slower than that because if the speed of memory addressing and the memory used for input expansion, it should still be under 1s. My hybrid TOTP generates a new code every 86.4s (1000 times per day), which gives enough time to enter and authenticate the code, so I would say the 6502 would be indeed able to produce an HMAC-SHA-1 hash from a single iteration input (time code), and format a truncated value for a user in a reasonable length of time.
It appears the CPU on a Tama-Go (more recent unit) is actually running at 8MHz, and is integrated into the display controller. It has 1536B of RAM and 320K of ROM, which should be more than enough to compute hash values.
Based on Poncho's comment, I looked up the instruction latencies for the 6502, they are around 6 cycles in the worst case, vs the pentium which is less than 1 (1469 instructions in 837 cycles) on average. If my 10x guess was accurate (it is not) that would mean 88ms for a hash iteration at 1MHz.
However, it appears the 6502 does not have variable bit rotations and shifts, it is 1 at a time, so my 10x guess is probably 20x off, although at 8MHz, that is still 1 HMAC-SHA-1 iteration in half a second.
If you want to try your hand at it, there is a web based simulator for the Tama-go, and you can find out for yourself how much code and cpu cycles are required to do the job.