Getting something to stick to asphalt or asphalt coated materials is a unique problem. Asphalt driveways have their own specific crack sealers and roofing materials generally use what we call "Plastic Cement". (One exception to this is a specially formulated polyurethane adhesive that will work on shingles.)
Plastic cement comes in a variety of formats. You can purchase it like an adhesive in a caulking cartridge and apply it directly from the gun. You can find rather fluid cans of it that can be applied with a spatula or stiff brush. You can find it also in a thicker format with fibre reinforcement (long fibres mixed right into the can) for better coverage over cracks.
It should be applied on a warm day. See WEATHER RESTRICTIONS: PLASTIC CEMENT.
It says to apply it to a "clean" surface, but that is a bit hard to define on a roof. What is important is to scrape away all dust and atmospheric grime -- you should be applying it to "scraped clean" asphalt -- and to solvent cleaned flashings. A rather quick wipe with solvent and steel wool is the best way to clean flashings without taking off any paint.
Some products require application to a dry surface, others can tolerate the surface being wet but there is an important trick with "wet" surfaces. You must work the plastic cement well into the surface actually forcing the water out like with a squeegee. You will see and feel when it is "floating" over the surface and when it begins to adhere. If you leave any water between the plastic cement and what you are applying it to, the sun will eventually turn that water to steam and you will get a boil that can eventually leak. Plastic cement won't mix with water but you must use it to push the water away.
It may surprise you but plastic cement has a very short life expectancy if exposed to the UV rays of the sun -- perhaps less than one year! So that pile of black mess that you smeared all over the joint between the chimney flashing and the brick is probably going to leak very soon. Never leave plastic cement exposed to the sun. Either apply it between two materials, like between two shingles to tab down the corners, or under the shingle to seal it to the flashing -- or cover it with a cap flashing, gravel or aluminum paint. Yes aluminum paint will stick to plastic cement if you wait one week to let it cure. A simple layer of aluminum spray paint will change the life expectancy of a plastic cement patch from one year to many years.
For one case history you may want to check out REPAIRING FLAT TOP ROOFS. If it is the bottom row of shingle tabs that are lifting check out GLUING THE BOTTOM ROW OF SHINGLES DOWN FLAT.