A bit of terminology first- for your application, I won't call the blockchain a private one but a Consortium or Federated blockchain. You don't want to give one person the authority to control the blockchain, but rather a group of individuals meeting certain requirements (as you mentioned it's a decentralized one). Additionally, it could also be made public (so that others may see it, even if it's maintained by a group of individuals or ogranizations).
It is very design requirement specific; let us learn from the Ethereum mainnet. (Over-estimating against our estimations)
From here, I can see that on a regular day, there were 1 million transactions per day on the Ethereum network. The underlying protocols for node to node communication in your network are superb enough to handle the traffic you need.
An average block sizes around 25kB and again on average 1000 transactions per block. For 40 million voters, we get to around 40,000 blocks times, and we get 1,000 megabytes- roughly 1GB then.
Of course this is very crude estimation, an you can make the system much more efficient based on your design principles. But, to answer your main question, you can do all this with bunch of normal computers- few citizens could participate in running the blockchain on their normal computers/ laptops and it would suffice to run the voting blockchain for the entire nation. Alternatively, you could dedicate Raspberry Pi (around $50 each) like single-board computers and that would do the job too.