A painting is either protected by copyright or it isn't; if it isn't it is in the public domain and anyone can do anything they want with it. If they make sufficient changes, the derivative work will have copyright on its own account.
Leonardo da Vinci's paintings are in the public domain. This is not because of the time since his death in 1519; it is because they were created before there was any copyright law.
Bob Ross' paintings are probably not in the public domain, however, this would need to be determined on a case by case basis using the applicable law at the time and in the place where each was published. Copyright laws change and the changes may or may not affect pre-existing works.
However, in both cases, photographs of the paintings will have their own copyright. These may or may not be in the public domain on a case by case basis.
I am explicitly not considering a "fair use" defence because based on your description you probably can't use one
I will be editing the works a bit as a core part of the application (minor stuff like adding a mustache on the Mona Lisa or a door in the middle of a Mondrian). Would editing the works like this be illegal?
If you are planning an adding a moustache to the actual Mona Lisa that hangs in the Louvre; that would be illegal on so many levels! Expect to die inside a French prison if the gendarmes don't "accidently" shoot you during the arrest.
If you are editing a photograph then providing you either have a) a photograph that is in the public domain or b) a photograph that you own or are licenced to use in that way; go for your life.
I will also be clear because "illegal" is an ambiguous word: copyright violation is not a crime that would be prosecuted by the state; it is a civil infraction of the copyright owner's property rights that they can take action on.
Would this be necessary or even make a difference?
If it is in the public domain then its not necessary and would not make a difference.
If it is subject to a licence then its necessary if the licence says it is. Leaving it out if it is required would breach the licence; putting it in if it wasn't would not make a difference.
If this is in fact true ...?
It isn't or isn't precisely. The expiration of copyright on a given work depends on where it was published and the laws of that country at the time it was published. Changes to the law can do strange things to the life of copyright. For example, see here for US origin works.
In addition, some works are in the public domain from the instant of their creation; in the US works created by US government employees are public domain as a matter of law, however, in Australia by contrast, government produced works have copyright owned by the Australian Government and follow the same rules as for privately produced works.
... would I be able to use the paintings for my purposes?
I will make it clear that I am not the artist and that I take no credit for the painting.
Good idea, irrespective of copyright status claiming works are yours when they are not is the tort of "passing off" - a common law doctrine with a much longer history than copyright.