'Which is more appropriate?' That really depends, on the gene and what you are looking for. 

However as a general rule of thumb its always good to use a couple different types. 

The most basic is Maximum Parsimony(Occam's Razor). It constructs a tree based on the fewest steps(SNPs) but evolution doesn't always work like this. So that is when you would use another tree ie Maximum Likelihood.  For the latter, you will need to ascertain a evolutionary model which predicts the modes of changes in the sequences. From that information you can put in the correct parameters to and create another tree which shows lineages calculated in another way. 

Before we go into that, do you have the original DNA sequences for these proteins? If so, try using DNA instead of AA for phylogeny.

If not, then use one of your favorite substitution model (WAG etc.) and do Maximum Likelihood search using RAxML (-f a option, with 100 rapid boostraps). One problem about AA sequence is that the substitution rate parameters are empirical, so they cannot be estimated from your data. If you want to know which model fits your data best, you can use jModelTest. 

Hi Robert,

For "which algorithm is more appropriate?", I suggest you follow the next link and you may start from subtitle "Analysis" ...

https://en.wikipedia.org/wiki/Maximum_parsimony_(phylogenetics)

 Regards,

For my opinion, don't use MEGA for protein analysis.

You can use PhyML or PAUP