Ideally, you should thaw it first. If you really need to cut frozen bologna, I recommend using a high-quality electric knife.