tl;dr You can't force MySQL to use a lot of cores.
40 million (4 crore) rows is a large, but not huge, database for MySQL. It is well within the capability of that software. You don't have to resort to desperate measures to get MySQL to work with that amount of data. You do have to index it correctly though.
MySQL can use a lot of CPU cores as of recent releases. But it doesn't use them to accelerate single queries; that sort of workload is not embarrassingly parallel. You can't get it to use a large number of cores for a single query. It simply doesn't work that way.
When it uses many cores, it uses them to handle simultaneous workload from many different connections. But of all those connections hit the same tables, it won't be able to use a lot of cores even if they are available.
At any rate, you should upgrade to version 5.7. It uses multithreading for more things than 5.6.
You will be able to improve performance with appropriate indexing for your query workloads. We can't advise you about that because you haven't offered any specifics about existing tables, indexes, queries, or simultaneous access by multiple clients.
Your server, with 20 cores and 64G of RAM, is overprovisioned in cores and RAM for MySQL, and for the sort of workload you mention. You didn't mention your server's I/O capabilities. I guess that replacing your mechanical disk drives with SSD drives using PCIe interfaces will make the most difference. But that's a guess based on little information.
My blunt advice: sell that massive server, or put it into service as a hypervisor host to use for lots of virtual machines for other things. It's overkill for MySQL.
Get a server with 16Gb and four fast cores. Use the extra money to provision it with as many PCIe SSD drives as you need for your application. Don't consider purchasing SSD drives smaller than about 0.2 terabyte; they are slower than the larger ones. Index your tables properly for your queries. For tables of the size you mention, don't worry about core utiization; instead worry about I/O.
You can probably try all this out for a few tens of dollars on a cloud virtual machine (Amazon, Rack Space, Digital Ocean) so you don't waste money on another overprovisioned server.
Best Answer
Turn OFF log_queries_not_using_indexes; it is virtually useless and can cause what you experienced.
If it is already off, then please show us one entire slowlog entry, together with the CREATE TABLE for the table(s) that are involved. Also, what version are you using?
On most systems it is best to set long_query_time to no more than 2.