OK, looking at that - I'd try a real arduino board rather than a clone, or at least a better clone.
I've found a through-PCB view of what appears to be that Arduino board, in the official version. It has a large ground plane area under the CPU with a good wide power track through near the top with what looks to be provision for a ceramic cap at the left and an electrolytic just above the right side:
The lower diagonal track is also power, but has no decoupling even on the official board, from what I can see.
Those capacitors do not appear to exist on your CPU board.
Or, if your board does have any obvious ground and power copper areas below the chip, soldering some ceramics caps (different values, large and small) flat to the board and directly across those may help.
Device data & pinout here:
https://www.farnell.com/datasheets/1817551.pdf
Atmel also have their own design notes covering the exact problem you are seeing, among other things.
**broken link removed**
For comparison with those boards, a seriously decoupled and filtered commercial design - no idea what it is, just from google images:
https://upload.wikimedia.org/wikipe...600px-CPU-Beschaltung-mit_MLCC-P1040239-d.jpg
That prototyping board is a ground-plane type, sometimes referred to as having a "colander ground plane" due to the array of clearance holes around the drilled holes.
It's one of these, the top with the normal stripboard pattern on the underside. I use the square pad ones as well for some things (better for RF).
https://docs-emea.rs-online.com/webdocs/138a/0900766b8138a6e6.pdf
You can get similar ground plane board from companies like Octopad.
Edit - just examined that PCB layout a bit closer; it looks like the large copper areas are topside, underneath the CPU. You would have to look for power and ground areas close outside the IC and see if there are any spots you could add caps to. There again, your board may be very different.
Can you post a photo of your board underside? I've found a lot of photos online that appear to be that exact board top view, but none of the back.
I did find a fully filtered version, at only about ten times the cost...
https://static1.squarespace.com/sta...32009cc69/1440849291799/mega8.jpg?format=500w