that would be awesome
and if 3ds could do it that would be even better. but i am not sure if they will 4 3ds because of sd card limits but who knows they might.
Simply use an algorithm or Nintendo's library to check how much space remains on the SD. If the remaining space is too low, then, warn the player.
I have also another idea about how this could be done.
First, you have a match (no matter if it's Player v Player or Player vs CPU)
-> During that time, the 3DS will record all inputs (Players/CPUs) in a temporary file.
Second, you wait for the match to end. We don't care about the results for now.
-> Ask the player if he/she wants to save a replay.
If the player says "Yes": -> Record all the inputs in a file that can only be read by the game (through an algorithm), and don't forget to precise (beginning of file) the rules, the stage, the teams (*) and the characters.
Otherwise: Delete the file from the 3DS's memory.
It can't be any easier to save space. That way, we could reduce the size from ~50+ Mb (if it's MPEG-4) to ~4-5 Mb (if it's a long match). Many games saves replay this way. And if you want to export your video, maybe there could be an "Export..." option available somewhere in the game, or simply wait for a tool that would allow conversion of the replay towards a readable video format (MP4/AVI...).
I know that seems hard to understand if you have limited knowledge in computing, but if needed, I can simplify the post.
*If you're playing with teams activated.