How badly would that affect storage? Might it even cause lag while playing O.O
I suppose that depends on what settings your new music is encoded with. The default records are .OGG vorbis files encoded at roughly 60 kbps, averaging a little over 3 minutes and about 1.3 MB each. 60 kbps, while fine for the minimalistic/simplistic style of C418's music, might be a little low for modern popular music like you'd hear on the radio; 128 is generally the minimum used by anyone, many prefer higher bitrates of 192, 256, or even 320 kbps. At higher bitrates, you might experience some lag, or at 60 kbps, you might find that it sounds pretty bad. Or, you might not notice at all. Maybe your computer could handle the higher quality just fine. And, some people can hear differences in sound quality much more than others -- as I said, some people prefer 256 or even 320 kbps for their digital music, but I personally cannot tell the difference between 128k and the original CD source material.
Like IronMagnus said, you could use a resource pack and convert it to the correct format. Or (this is just a guess) you could find the folder storing the music, a change one of them to the music you want, (keep the name the same, so it reads it) and if you know what disc it uses it may work. Though that's just a guess, I'll look into it later on.
I don't know if this is still the case, but it used to be that when you did this, the game would find out about it somehow, and replace the original files. Finding the files is easy enough, they're all stored in .minecraft/assets/records.
The resource pack method works like this:
Create a resource pack, then follow this and place the .ogg inside the records folder. You should only need to do that.