If I were to format the memory on my 3DS, and have all of the games I downloaded deleted, can i redownload them from the eshop? Or does formatting the memory also erase my receipts from downloading the games, so i can't redownload them? And would having my club nintendo account linked to the eshop help me redownload them in any way?
No, unlike the Wii, if you format your 3DS system memory, you will lose all the licenses for the software you downloaded, and you will not be able to download them again for free. Also, if you save your games to an SD card and format your system memory, you will no longer be able to play the games that you saved on your SD card.
Linking your eShop account to your Club Nintendo account does nothing but keep track of your downloads in Club Nintendo and possibly make you eligible for coins. It does not make it so you can re-download games after formatting your system memory.
As a note, BeardedOne's response is out of date. Whether you are able to download a game is a matter of which 3DS console the game is authorized for. Therefore if you format/upgrade your SD card, you can still re-download the game on the 3DS it was purchased on.
That said, if you do not back up your saved data, that will all be lost after a format. To backup your saved data, you should be able to just copy the files to a computer and then copy the files back to the SD card after the format.
To Redownload a game: just search for the game you previously bought. When you get more info about the game there should be a big button named "Redownload". If there isn't and it's a button to buy the game, then the 3DS you're on wasn't authorized for that game.