In the general consensus, it's up to the DM. Most people trying to argue against a paladin needing a God's argument is pretty weak based on the fact that you're only arguing about needing it.
Its less "arguing against" and more "pointing out what the rules actually say".
Its
always up to the DM in the end, whether that is Paladins needing to worship something, or Wizards only coming from a single nation in the setting.
So let's think about this. Suppose the paladin only needed faith in a principle, it's virtually the same thing. You can take a divine out of the picture and replace it with say for example justice. This will be harder for the paladin, because if he strays or falls, he can never redeem himself. If he feels his principles aren't strong enough that he has to make a deal with an entity for more power, he should immediately lose his paladin powers. His own lack of faith will be his undoing. This isn't even getting into what if the entity he made a deal with forces him to do things that contradicts his principles. Whether a paladin is a holy warrior of a god, or of justice, it's just hard to see them taking a back door deal and it's ok. A fighter/warlock who may have been a paladin at one point makes sense story-wise.
It is the Oath of a Paladin that grants them their abilities. Whether that oath is sworn to a deity, or to their ancestors, or the blood of their murdered family, or anything else.
Now it is entirely possible, as you say, for a Paladin to fail to uphold their Oath. I'm not seeing why they would not be able to redeem it if they didn't worship a deity though. Its not the deity granting the power in the first place.
The Oath of Vengeance is to swear to defeat a specific evil whatever the cost. A devil offering just the right amount of power at the right time to help the Paladin achieve that is going to have a
seriously tempting offer.
Remember that not all Warlocks have made a conscious choice to engage in a pact with another entity, and the cost isn't always going to be the warlocks soul, service, or anything that contradicts their principles.
I've had a celestial pact warlock become a Paladin by swearing their oath to their patron - I'd imagine that that would be relatively common amongst Oath of the Ancients paladins as well.