You say "the SLAM algorithm" - which one? There are dozens, if not more out there.
I personally think that Tiny SLAM could be implemented on an Arduino Mega 2560, with a 512K SRAM expansion board - and perhaps a SD card. At only 200 lines of C code, it shouldn't take much.
The main downside would probably be speed - all the memory in the world won't help you if your SLAM code is loping along like an asthmatic jogger. Even if you boosted the Mega to run at 20 MHz instead of 16 - that still would likely be a bottleneck. Then again, AFAIK, nobody has tried putting Tiny SLAM on an Arduino...maybe you could try it out?
Or - maybe Tiny SLAM could be divided up (not sure - I haven't looked at the code much) and split over multiple Arduino Mega boards; essentially a low resources parallel cluster, if you will (use SPI as the interconnect - or a custom parallel interface).
Despite all of this, and even though it might not be fast, it would be a great learning opportunity - you could essentially re-implement the Stanford Cart or one of the other early auto-nav robots (it would probably process the data faster compared to them, too).
Alternatively - it might be possible to implement a really scaled down SLAM algorithm, where the map is essentially a rough grid of cells, perhaps with just a few levels of probability - perhaps not super-accurate, but maybe fast to process and could likely fit on an Uno (for a small map, anyhow).
If ultimately the small form factor is the need - then there are plenty of ARM-based SOC boards out there that are more than small enough, on which Tiny SLAM or some other more complex SLAM algorithm could be run (ie - the Raspberry Pi, Banana Pi, Orange Pi, BeagleBone, Pine A64, etc).