I would do it weekly or every other week. That's just me. All the poop and uneaten food just settles down there, no reason not to just suck it all out if you have no live plants. You could do half one week and half the next.
How much water you should change depends on what species of fish you have and how much waste they produce. I like aqadvisor.com if you enter the tank size and fish it'll tell you how much to change weekly. I personally feel like 15% is not adequate especially if the other fish are mollies. I would do 30-40% each week. I do 50% right now. No reason to only do one 35-50% change each month. I'd just do the same each week and find a balance. Test the nitrates and see how much you need to change to keep them down at a good level.
Also on the note of filter pad changing, what kind of filter do you have? You may know this already, but If it has a "bio-wheel" or permanent sponge or substrate thing to house the good bacteria you may (not 100% sure I don't replace mine) be okay replacing it. But if the filter pad you are replacing is the only medium in the filter, replacing it could really cause issues. The filter pads house a lot of good bacteria and replacing sound cause ammonia spikes, which, if you've done it in the past and the fish lived, it still isn't good for them.