Depends on the internals. If you under clock a 5870 to 600MHz its still going to blow away a 4870 at 750MHz, architecture and core count makes a much larger difference than the speed of the GPU. The memory only comes into play at higher resolutions, 512 is fine up until you hit 1920x1080, at which point 1GB gives a slight advantage.
What two cards are you considering? Link to them if you can.
Well first major difference is that the 1GB one is using DDR2 and the 512MB one is using GDDR3 so that would boost its performance a bit. Something about those specs is very wrong though. The 4650 had a core speed of 600MHz or 650MHz not 750MHz like the second one has, the 1GB one also asks for a PCI-E power cable which it really shouldnt.
Anyway, if those specs are true the 512MB one has the faster memory, and faster core clock which would make it faster all around.
The 512MB version of the card uses GDDR3 as opposed to GDDR2. Of the two, the 512MB GDDR3 will be the better choice. The 4650 can't utilize 1GB of memory, so you'd be better going with the faster GDDR3 card.