Is it good to label papers as Part I, Part II? If a paper is too long, I was advised to split it into two papers. What is the general opinion of reviewers/editors on having "Part I", "Part II" literally in the title of the papers?

Or is it better if I replace "Part I", "Part II" by more descriptive titles?

Thanks. (My field is in Math.)
You can do that, though a better approach may be to title them something like


  Hypersingular monoids in graph theory. Part I: Definitions and basic properties


and then


  Hypersingular monoids in graph theory. Part II: Applications to semiregular smoothness theory of spiked stars


This way, you're a bit more expressive than just part 1 and 2.

The downside of this approach is that good journals will ask you to make sure that either "Part I" is already self-contained and of independent interest (which is probably difficult to achieve if you are currently splitting up something you've already written), or that you submit the two parts together (so that the combined oeuvre can be reviewed as a whole). The latter, of course defeats the purpose of splitting it in the first place.

Long papers are a hassle all around. It's difficult to get them through the review process, and much depends on what concretely you have in the paper(s). As a consequence, there is little that can be said in terms of specific advice in your situation without knowing the details of the paper. Talk to some of the experienced people in your field about the situation and ask them how they would suggest you handle it!