In my opinion three or four calls of get_template_part() is perfectly acceptable and even within the norm for some of the larger and more complex themes out there.
I don’t know how many is too many but I think it would have to be a pretty large number to notice a hit in performance.
A Deeper Look
get_template_part() calls locate_template().
locate_template() uses a foreach() loop to run file_exists() against your theme directory.
Performance of file_exists()
According to this post about the performance of file_exists(), PHP automatically caches the results of the function to improve performance. Overall it is considered to be rather fast.
Performance of foreach()
This post about the performance of foreach() vs for() concludes that generally there is little discernible difference between the two. However, it doesn’t directly address the performance of foreach() on its own. For that, this post on how foreach() really works dives deep into the function. It states the following.
1.foreach() can be slow because it has to copy the array but in most cases usually isn’t.
2.foreach() is usually transparent in its behavior.
3.foreach() can behave strangely if the array is modified within the loop.
In summary
It would appear that a call to get_template_part() should be relatively quick. A loop within locate_template() must be used and foreach() appears to be as good a tool for the job as any other. file_exists() will then cache its results. The only direct control we have over the performance of get_template_part() is the number of files within the template directory.
Unless you have hundreds of template files to look through or are making an equally silly number of calls to get_template_part() the change in your site’s performance should be negligible.