Can bitcoins be split up into greater than a billion parts?
The Bitcoin protocol doesn't allow you to easily have denominations lower than a satoshi (10^-8 bitcoins). But once there is a need and widespread agreement, it can be modified to allow it.

Destroyed bitcoins however will not have any significance as a factor contributing to this need.