I wouldn't undo your partitions. I haven't used the mandrake rescue disk since 7.1, but there is a way to do it using a Knoppix cd, so it might work with the disk you have. Basically, you use the cd to boot, mount the partition(s) you need to work on, then use the 'chroot' command, which allows you to pretend you booted your dead system. Once that's ready, it's just a matter of fixing /etc/lilo and running /sbin/lilo. It's not hard, but it's hard to tell you details without exact information on your partitions. You can find most of this stuff by googling or searching LQ a little, though.
You can also install grub in a similar fashion, but I'd probably prefer to get lilo working again, and then deal with another bootloader. There's not usually ever a reason to reinstall Linux, but without some experience, sometimes it's the easiest option. But I most definitely wouldn't undo your partition setup, because there's no reason to. If you decide to reinstall, your next distro will happily find that partition, and it will save you some time and hassle.